分析一个我第一次见的素数测试函数¶

今天逛到这个连接，发现其中的第四种素数判定方法很有意思：

#include<stdio.h>
#include<math.h>
int p[8]={4,2,4,2,4,6,2,6};
int prime(int n)
{
    int i=7,j,q;
    if(n==1)return 0;
    if(n==2||n==5||n==3)return 1;
    if(n%2==0||n%3==0||n%5==0)return 0;
    q=(int)sqrt(n);
    for(;i<=q;){
        for(j=0;j<8;j++){
            if(n%i==0)return 0;
            i+=p[j];
        }
        if(n%i==0)return 0;
    }
    return 1;
}
void main()
{
    int n;
    scanf("%d",&n);
    if(prime(n))puts("Yes");
    else puts("No");
}

仔细研究发现，这里利用的是这样的原理：

判断是不是 1, 2, 3, 5 及其倍数
从 7 开始，不断考虑其是否是素数，那么，这个 p 是什么回事呢？

首先把 p 的各个元素加起来，和为 30，然后就可以发现一个规律： 7 为质数，7+2=9 不是质数，7+4=11 为质数，11+2=13 为质数，13+2=15 为合数，15+2=17 为质数，17+2=19 为质数，19+2=21 为合数，21+2=23 为质数，23+2=25 为合数，25+2=27 为合数，27+2=29 为质数，29+1=31 为质数，31+2=33 为合数，33+2=35 为合数，35+2=37 为质数。观察以上所有的合数，都含有 2 或者 3 或者 5 的因子，而 30 又是 2,3,5 的公倍数，也就是说，后面的素数模 30 的余数不可能是上面这些合数，而剩下的素数才可能是真正的素数，于是跳过了很多素数的判断。

至于这个函数的性能如何，还需要进一步测试来进行判断。

分析一个我第一次见的素数测试函数¶

评论