4

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?

Community
  • 1
  • 1
Waypoint
  • 17,283
  • 39
  • 116
  • 170

3 Answers3

19

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)).

Yick Leung
  • 1,048
  • 1
  • 9
  • 16
vissi
  • 2,325
  • 1
  • 19
  • 26
  • A loop *like* that, but preferably which doesn't test 0 or 1 as factors ;-p – Steve Jessop Mar 12 '11 at 09:57
  • You can further optimise by first checking `num % 2` then starting i from 3 and incrementing by 2 as you'll have already eliminated all even numbers. – Lazarus Mar 12 '11 at 09:57
  • some say that 1 is also prime... – MoonBun Mar 12 '11 at 12:12
  • 2
    @Vlad: for the last 100 years or so that has not been the convention among mathematicians, so "some" are either contrarian or dead. Obviously if you want to use an unusual definition of "prime" then you need unusual code. With this code you also need to be aware that `is_composite(n)` shouldn't be implemented as `!is_prime(n)` if it's supposed to give the right answer for 1, since 1 isn't composite either. – Steve Jessop Mar 12 '11 at 12:18
  • Shouldn't the first two lines read: if (num <= 1) return false; if (num % 2 == 0) return false; Also num==2 is untested. – Hugues Fontenelle Nov 02 '12 at 18:58
  • You need to fix the two first lines of code where you test `i`, where you want to check `num`. – gsamaras Aug 29 '14 at 21:46
5

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.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • And with a few code lines before table look-up the memory can be reduced to 256M as there is no need to have a bit for even numbers if an odd-even check is made before look-up. – Support Ukraine Apr 05 '21 at 07:13
4

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.

rsc
  • 4,234
  • 2
  • 30
  • 28