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

上面的代码是朋友为获得素数而写的东西.它似乎正在使用某种筛分,但我不确定它是如何起作用的.下面的代码是我不那么棒的版本.我会用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;
}

我的问题是:他究竟在做什么？

Answer 1

你朋友的代码正在利用这样一个事实:对于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在循环体中.