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

上面的代码是一个朋友为了得到一个素数而写的。它似乎在使用某种筛分，但我不确定它是如何工作的。下面的代码是我不太棒的版本。我会使用sqrt我的循环，但我看到他在做其他事情（可能与筛分有关），所以我没有打扰。

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

我的问题是：他到底在做什么？

4

5 回答 5

5

你朋友的代码利用了这样一个事实，即对于 N > 3，所有素数都采用 (6×M±1) 的形式，对于 M = 1, 2, ...（所以对于 M = 1，素数候选者是 N = 5 和 N = 7，这两个都是素数）。此外，所有素数对都像 5 和 7。这只检查每 3 个奇数中的 2 个，而您的解决方案检查 3 个奇数中的 3 个。

您朋友的代码正在使用除法来实现类似于平方根的结果。也就是说，条件divisor <= n / divisor或多或少等同于，但比溢出更慢且更安全divisor * divisor <= n。unsigned long long max = sqrt(n);在循环外使用可能会更好。与搜索更多可能值的建议解决方案相比，这大大减少了检查量。平方根检查依赖于这样一个事实：如果 N 是复合的，那么对于给定的一对因子 F 和 G（使得 F×G = N），其中一个将小于或等于 N 的平方根，并且另一个将大于或等于 N 的平方根。

正如Michael Burr所指出的，朋友的素数函数将 25 (5×5) 和 35 (5×7) 识别为素数，并生成 1000 以下的 177 个数作为素数，而我相信，该范围内只有 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

于 2012-04-23T04:48:59.433 回答
2

他正在检查基础 6k+1/6k-1，因为所有素数都可以用这种形式表示（所有整数都可以用 6k+n 的形式表示，其中 -1 <= n <= 4）。所以是的，它是一种筛分形式……但不是严格意义上的。

更多信息： http ://en.wikipedia.org/wiki/Primality_test

于 2012-04-23T04:44:19.470 回答
1

如果 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 -> 不明显复合

我以前没见过这个小技巧，所以它很简洁，但效用有限，因为埃拉托色尼筛子更有效地找到许多小的素数，而更大的素数则受益于更快、更智能的测试。

于 2012-04-23T05:05:52.150 回答
0 
#include<stdio.h>
int main()
{
    int i,j;
    printf("enter the value :");
    scanf("%d",&i);

    for (j=2;j<i;j++)
    {
        if (i%2==0 || i%j==0)
        {
            printf("%d is not a prime number",i);
            return 0;
        }
        else
        {
            if (j==i-1)
            {
                printf("%d is a prime number",i);
            }
            else
            {
                continue;
            }
        }
    }
}
于 2021-07-04T16:24:20.747 回答
-1 
#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;
}
于 2016-02-02T09:15:45.983 回答