How to Efficiently Determine if a Number is Prime in C?

How to Determine Prime Numbers in C

The question discusses determining whether a given integer is prime in C. The original C# solution provided was:

static bool IsPrime(int number)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0 && i != number)
            return false;
    }
    return true;
}

To understand how to implement this in C, let's break down the algorithm:

1. Check if the number is negative, zero, or one. These are not prime.
2. Iterate from 2 to the square root of the number.
3. For each iteration, check if the number is divisible by the current value.
4. If divisible, the number is not prime.
5. If the loop completes without finding a divisor, the number is prime.

Translating this algorithm into C, we get:

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

Differences from the original C# solution include:

• bool is not a C data type, so we use int and return 0/1 instead.
• stdbool.h is not assumed to be available, so we declare i manually.
• The loop iterates up to the square root of the number for efficiency.

The above is the detailed content of How to Efficiently Determine if a Number is Prime in C?. For more information, please follow other related articles on the PHP Chinese website!