Prime number in C

Question

int prime(unsigned long long n){
    unsigned val=1, divisor=7;
    if(n==2 || n==3) return 1; //n=2, n=3 (special cases).
    if(n<2 || !(n%2 && n%3)) return 0; //if(n<2 || n%2==0 || n%3==0) return 0;
    for(; divisor<=n/divisor; val++, divisor=6*val+1) //all primes take the form 6*k(+ or -)1, k[1, n).
        if(!(n%divisor && n%(divisor-2))) return 0; //if(n%divisor==0 || n%(divisor-2)==0) return 0;
    return 1;
}

The code above is something a friend wrote up for getting a prime number. It seems to be using some sort of sieving, but I'm not sure how it exactly works. The code below is my less awesome version. I would use sqrt for my loop, but I saw him doing something else (probably sieving related) and so I didn't bother.

int prime( unsigned long long n ){
    unsigned i=5;
    if(n < 4 && n > 0)
        return 1;
    if(n<=0 || !(n%2 || n%3))
        return 0;
    for(;i<n; i+=2)
        if(!(n%i)) return 0;
    return 1;
}

My question is: what exactly is he doing?

Answer 1

Your friend's code is making use of the fact that for N > 3, all prime numbers take the form (6×M±1) for M = 1, 2, ... (so for M = 1, the prime candidates are N = 5 and N = 7, and both those are primes). Also, all prime pairs are like 5 and 7. This only checks 2 out of every 3 odd numbers, whereas your solution checks 3 out of 3 odd numbers.

Your friend's code is using division to achieve something akin to the square root. That is, the condition divisor <= n / divisor is more or less equivalent to, but slower and safer from overflow than, divisor * divisor <= n. It might be better to use unsigned long long max = sqrt(n); outside the loop. This reduces the amount of checking considerably compared with your proposed solution which searches through many more possible values. The square root check relies on the fact that if N is composite, then for a given pair of factors F and G (such that F×G = N), one of them will be less than or equal to the square root of N and the other will be greater than or equal to the square root of N.

---

As Michael Burr points out, the friend's prime function identifies 25 (5×5) and 35 (5×7) as prime, and generates 177 numbers under 1000 as prime whereas, I believe, there are just 168 primes in that range. Other misidentified composites are 121 (11×11), 143 (13×11), 289 (17×17), 323 (17×19), 841 (29×29), 899 (29×31).

Test code:

#include <stdio.h>

int main(void)
{
    unsigned long long c;

    if (prime(2ULL))
        printf("2\n");
    if (prime(3ULL))
        printf("3\n");
    for (c = 5; c < 1000; c += 2)
        if (prime(c))
            printf("%llu\n", c);
    return 0;
}

---

Fixed code.

The trouble with the original code is that it stops checking too soon because divisor is set to the larger, rather than the smaller, of the two numbers to be checked.

static int prime(unsigned long long n)
{
    unsigned long long val = 1;
    unsigned long long divisor = 5;

    if (n == 2 || n == 3)
        return 1;
    if (n < 2 || n%2 == 0 || n%3 == 0)
        return 0;
    for ( ; divisor<=n/divisor; val++, divisor=6*val-1)
    {
        if (n%divisor == 0 || n%(divisor+2) == 0)
            return 0;
    }
    return 1;
}

Note that the revision is simpler to understand because it doesn't need to explain the shorthand negated conditions in tail comments. Note also the +2 instead of -2 in the body of the loop.

Answer 2

He's checking for the basis 6k+1/6k-1 as all primes can be expressed in that form (and all integers can be expressed in the form of 6k+n where -1 <= n <= 4). So yes it is a form of sieving.. but not in the strict sense.

For more: http://en.wikipedia.org/wiki/Primality_test

Answer 3

In case the 6k+-1 portion is confusing, note that you can perform some factorization of most forms of 6k+n and some are obviously composite and some need to be tested.

Consider numbers:
6k + 0 -> composite
6k + 1 -> not obviously composite
6k + 2 -> 2(3k+1) --> composite
6k + 3 -> 3(2k+1) --> composite
6k + 4 -> 2(3k+2) --> composite
6k + 5 -> not obviously composite

I've not seen this little trick before, so it's neat, but of limited utility since a sieve of Eratosthenese is more efficient for finding many small prime numbers, and larger prime numbers benefit from faster, more intelligent, tests.

Answer 4

#include<stdio.h>

int main()
{
   int n, i = 3, count, c;

   printf("Enter the number of prime numbers required\n");
   scanf("%d",&n);

   if ( n >= 1 )
   {
      printf("First %d prime numbers are :\n",n);
      printf("2\n");
    }

   for ( count = 2 ; count <= n ;  )
   {
      for ( c = 2 ; c <= i - 1 ; c++ )
      {
     if ( i%c == 0 )
        break;
  }
      if ( c == i )
      {
         printf("%d\n",i);
         count++;
      }
      i++;
   }

   return 0;
}