Geek asks and answers

Main number in C

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 what a friend wrote to get a simple number. It seems to be using some sort of sifting, but I'm not sure how this works. The code below is my less surprising version. I would use sqrtfor my cycle, but I saw how he was doing something else (maybe sifting), and therefore I was not worried.

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?

+3
source share
4 answers

, N > 3 (6 × M ± 1) M = 1, 2,... ( M = 1 N = 5 N = 7, ). , 5 7. 2 3 , 3 3 .

- . divisor <= n / divisor , , , divisor * divisor <= n. unsigned long long max = sqrt(n); . , . , N , F G (, F × G = N), N N.

, 25 (5 × 5) 35 (5 × 7) , 177 1000 , , , 168 . 121 (11 × 11), 143 (13 × 11), 289 (17 × 17), 323 (17 × 19), 841 (29 × 29), 899 (29 × 31).

:

#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;
}

.

, , divisor , , .

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;
}

, , . +2 -2 .

+5

6k + 1/6k-1, ( 6k + n, -1 <= n <= 4), , .. .

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

+2

6k + -1 , , 6k+n, , , , .

:
6k + 0 →
6k + 1 → 6k + 2 → 2 (3k + 1) →
6k + 3 → 3 (2k + 1) →
6k + 4 → 2 (3k + 2) →
6k + 5 →

I haven’t seen this little trick before, so it was neat but limited, as the Eratosthenese sieve is more efficient for searching, many small primes and large primes benefit from faster, more intelligent tests .

+1
source 
#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;
}
-1
source

More articles:


All Articles