C Language Prime Number Check (Optimized Version)

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Determining whether a number is prime is a classic case in C language, involving a combination of loops and conditional statements.

Implementation Idea

The basic idea for checking whether a number<span>n</span> is prime:

1. A prime number must be greater than 1
2. Check divisibility of n from 2 to (the square root of n)
3. If there exists a number that divides n, then n is not prime; otherwise, n is prime

Optimization: It is sufficient to check up to<span>√n</span> because if n has a factor greater than<span>√n</span>, it must have a corresponding factor less than<span>√n</span>.

#include <stdio.h>
#include <math.h>  // Using sqrt() function
// Function to check if a number is prime, returns 1 if true, otherwise returns 0
int isPrime(int n) {    // Handle special cases    if (n <= 1) {        return 0;  // Numbers 1 and less are not prime    }    if (n == 2) {        return 1;  // 2 is prime    }    if (n % 2 == 0) {        return 0;  // Even numbers are not prime (except 2)    }
    // Check odd numbers from 3 to sqrt(n) for divisibility
    int sqrtN = (int)sqrt(n);    for (int i = 3; i <= sqrtN; i += 2)     {        if (n % i == 0)         {            return 0;  // Found a divisor, not prime        }    }
    return 1;  // No divisors found, is prime}
int main() {    int num;    while (true)    {        printf("Please enter an integer: ");        scanf_s("%d", &num);
        if (isPrime(num)) {            printf("%d is prime\n", num);        }        else {            printf("%d is not prime\n", num);        }    }    return 0;}

Code Analysis

1. Special Case Handling

• Numbers less than or equal to 1 are not prime
• 2 is the only even prime number
• All other even numbers are not prime (can be excluded directly)

2. Loop Check

• Only need to check up to the square root<span>n</span> (using the<span>sqrt()</span> function)
• Only check odd numbers (since even numbers have been excluded)
• Step size of 2 (<span>i += 2</span>), improves efficiency

Optimization Explanation

This implementation has two significant optimizations compared to the most basic method:

1. Excluding Even Numbers: All even numbers except 2 are not prime, so they can be excluded directly, reducing the number of checks by half

2. Checking Up to the Square Root: For a number n, if it has a factor greater than √n, it must have a corresponding factor less than √n, so it is sufficient to check up to √n

Conclusion

Through this example, we learned:

1. The mathematical definition and logic for determining prime numbers
2. How to implement prime number checking using loops and conditional statements
3. The basic idea of program optimization (reducing unnecessary calculations)
4. Function encapsulation and invocation

This program, while simple, is a great example for learning logical thinking in C language.