C - how to test easily if it is prime-number? [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicates:

C - 开发者_开发知识库determine if a number is prime

Is there any way to test easily in C whether a selected number is prime or not?

---

The easiest way is writing a loop, like:

int is_prime(int num)
{
     if (num <= 1) return 0;
     if (num % 2 == 0 && num > 2) return 0;
     for(int i = 3; i < num / 2; i+= 2)
     {
         if (num % i == 0)
             return 0;
     }
     return 1;
}

You can then optimize it, iterating to floor(sqrt(num)).

---

The fastest way is to precalculate a bit array (indicating prime/nonprime) of all possible integers in the range you're interested in. For 32-bit unsigned integers, that's only 512M, which will easily fit in modern address spaces (and, even if it didn't, it would be a fast file lookup).

This will almost certainly be faster than calculating it via a sieve each time.

---

You could try to use Sieve of Eratosthenes:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Easily you will find various implementations of this algorithm.