快速判断区间类质数的个数方法探讨

2022-02-14

怎样快速判断某个区间 [a，b] 里面有多少个质数？这个题目来源于2021年秋C语言重修班期末考试上机试题试题8。

众所周知，快速判断一个整数是否是素数可以用以下 C 语言代码来实现：

int isPrime(int n){
    int i,flag =0;
    for(i=2; i<=n/2; ++i){
     if(n%i==0){
            flag=1;
            break;
        }
    }
    if (flag==0)
        return 1;// 是素数,返回1
    return 0;	//默认返回0
}

通过蛮力法罗列区间 [2，100]的素数：

输出结果为：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97。除掉 2 和 3，剩余的数字加上 1 或者减去 1 都是 6 的倍数？因为：5=6 * 1-1，7=6 * 1 + 1，11 = 6 * 2 - 1， 13 = 6 * 2 + 1，… , 这个猜想是否代表着所有的质数（除掉 2 和 3）都能表示成 6 的倍数加或者减1？或者说6的倍数加或者减1一定是质数？也就是数理逻辑上的充分必要性。

废话不多说，先上测试代码：

#include <stdio.h>
#include <stdlib.h>

int isPrime(int n){
    int i,flag =0;
    for(i=2; i<=n/2; ++i){// 符合该条件不是素数
     if(n%i==0){
            flag=1;
            break;
        }
    }
    if (flag==0)
        return 1;
    return 0;
}
int main() {
    int p;
    for(int p = 4; p<=10000;p++){
        if(isPrime(p)){
            printf("0，%d\n",p);
            if((p+1) % 6 == 0 || (p-1) % 6 == 0){
                // do nothing
            }
            else{
                //1，是质数但是不能被分解成 6n+1 和 6n-1，打印出来
                printf("1，%d\n",p);
            }
        }
    }
    for (int i = 0; i < 10000; ++i)
    {
        if(isPrime(6*i+1)|| isPrime(6*i-1)){
            // do nothing
        }else{
            //2，满足 6n+1 和 6n-1但不是质数，打印出来
            printf("2，%d\n",i);
        }
    }
}

暂时得出的结论是：所有的质数一定能分解成 6 的倍数加减 1，但是 6 的倍数加减 1并不是都是质数。后者的一个反例是：121，121=6 * 20 + 1，但是 121 显然不是质数。需要注意的是我们是通过计算机程序在有限的区间里面观察到这个现象，代替不了数学上的严格证明! 所以我在得出的结论前面加上了暂时二字。不过好在计算机程序只要求计算在某个区间上的质数的个数，在一定程序上规避了这个证明。

回到开头的那个问题，怎样快速判断某个区间 [a，b] 里面有多少个质数？按照上面的分析，可以按照 6 的倍数穷举，然后再进行二次判断即可，注意 a 是否大于等于3。代码不再在此赘述。