筛法求质数 之 埃式筛
|
3,131
|
算法
|
tdiant

现在有这样的一个题目

输入格式
一行两个整数 询问次数n，范围m
接下来n行，每行两个整数 l,r 表示区间

输出格式
对于每次询问输出个数t，如l或r∉[1,m]输出 ERRER

范围
1<=n<=1000
1<=m<=1000000
-10^9<=l<=r<=10^9
1<=t<=1000000

这道题关键问题就是我们需要知道怎样求出A到B内究竟有多少质数。那么我看到这个题就形成了一个这样的思路：

  1. 输入A和B，写个循环遍历A到B里的每个数，定义一个变量total来存有多少个质数。
  2. 判断当前这个循环到的数是不是质数，如果是，给total加1。
  3. 输出total就完事了。

好，我想到了就赶紧写，我这么写：

#include <stdio.h>

int isPrime(int n);

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a > b || a > m || b > m) {
            printf("ERRER\n");
            continue;
        }

        int sum = 0;
        for (int j = a; j <= b; j++) {
            sum += isPrime(j) ? 1 : 0;
        }

        printf("%d\n", sum);
    }
    return 0;
}

int isPrime(int num) {
    if (num <= 1)
        return 0;
    for (int i = 2; i <= ((num + 1) / 2); i++) {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

问题出在哪儿？

每个人的写法都不一样，但是思路大致是一样的，都是每个数都开一个for循环再去找有没有这样的因子。

但是想一个问题，这道题问的是多个问题，他问的区间有很多个，那么好，我这样问：

请问1到10000有多少个质数？请问2到10000有多少个质数？请问3到10000有多少个质数？

显然，如果他这样问，举个例子，比如6789这个数字，就得跑3遍这样的for循环去找他的因子。我明明是找过了的，又要再找一遍，问一次就得找一次，效率太低。
并且，1到10000，我们分析分析时间复杂度，判断一个数字是不是质数，可能时间复杂度可以被算成O(n)，那1到10000都要算一次呢？这个O(n)的算法被执行了10000遍，那时间复杂度是……
是不是很大啊！这个程序用的时间太多了！

如何解决这个问题？

我刚才就觉得很气，明明是6789这个数我算过一次是不是质数了，又让我再去找一次是不是质数。
琢磨一下这个问题，如果现在我有一张表，这张表是我程序刚运行，还没开始接受题问的时候就提前准备好的，它记录着每个数字是不是质数，这个表长这个样：

数字 0 1 2 3 4 5 6 7 8
是质数？ 不是 不是 是 是 不是 是 不是 是 不是 是

然后他再问我6789是不是质数，我看一眼这个表，这个表上写着6789不是质数，好，我马上告诉你6789不是质数，你问多少遍我就给你查多少次表。要明白，查表这个操作不是算数，基本上不需要什么时间，我可以直接认为查表不用时间，这不就很快嘛？

这样我们就解决这个问题了。如果我们程序一开始运行，先去准备这样的一个“表”，你问我这个数字是不是质数，我给你看一眼表上怎么写的，你问我的时候我就可以对答如流，我不用再去算了，时间就节约了不少。

这个表我可以用数组做。
如果有这样的一个数组是这样定义的：int a[10050];（我开的稍微大一点，稳妥些），我用1代表是质数，0代表不是质数，我就可以判断a[6789]是不是1，如果是1，那6789是质数，如果是0，6789就不是质数了。

表怎么来？

说的这么好，那么表究竟怎么来呢？

常规的方法

有一种低效的方法就是跟以前一样，循环遍历1到10000，再去挨个找每个数是不是能找到因数呀，如果能找到给他记上0，找不到就记1呗。
害，这方法效率太低。实际上，早就有一些数学家发明了更厉害的方法了。

筛法求素

隆重介绍筛法求素数的方法。其中一种方法，叫做埃式筛。这种筛法后续被欧拉进行了改进，发明了欧拉筛。
顾名思义，筛法的思想就是，我依次判断1到10000每个数是不是素数的过程并不是找因数，而是通过“筛选”得来的。

想一个问题，如果我知道a这个数字是质数，这意味着什么？
其实这也意味着我能淘汰别的一些数字了。比如我可以直接告诉你，a*a不是质数。
这样一琢磨，嘿，其实 a*(a+k)，k>=0 ，这些数字你都能淘汰掉了。
筛法的根本思想就是：我知道了一个质数，可以知道一系列数字不是质数，最巧妙的是，每个数字都会因为之前的筛选，被合理的准确且稳定地得以判定是否为质数。

埃式筛法

埃式筛法是常用筛法的一种。

基本思路

OK，现在我们做一个这样的数组，数组我先想办法让每个元素都是1，也就是一开始我们认为每个数字都是质数，后面慢慢筛选去掉不是质数的数字。由于数组相当于表，我们按照表来理解。
这个表我先放进去三个一开始我规定好的规则：

数字 1 2 3
是质数嘛 0（代表不是） 0（代表不是） 1（代表是）

后面我们统一用0代表不是，1代表是素数。

这也就是相当于我这样写了：a[0]=0; a[1]=0; a[2]=1;

你想一想，我们写一个循环，把2到10000都挨个看一遍，假设循环变量是i。
我们先看看i自己是不是质数。由于从2开始，2我们规定是质数。
好，我们发现a[i]==1成立，那么我们再在这个循环里开一个新循环，这个循环用来根据这个质数淘汰已知合数。循环变量是j，j从i*i也就是4开始看起，j每次都加i，那么我们这个循环一直让a[j]=0，达到淘汰的目的。

由此一直循环下去，举个例子，看看i=3的时候。
循环发现a[i]==1成立，判定3是质数，又开了个循环把33、33+3、33+3+3、33+3+3+3以此类推都弄成了0，淘汰掉了一系列数字。

然后继续循环下去，i=4了。4是合数，不管，pass。然后i=5了，发现是合数，又开了个循环淘汰掉了55、55+5、5*5+5+5，以此类推。

这样i从1到10000一遍下来，该淘汰的都淘汰掉了。恭喜你，现在a这个数组就是我们要的质数表了！以后谁问我们什么数字是不是质数，直接看a[这个数]是不是等于1就行了。

为什么是i * i？

埃式筛这种方法有个问题，如果我i循环到了5，肯定要开循环淘汰别的数字了对吧，那为啥我这个里面的循环从i*i开始看，而不是从i*2开始看呢？难道5*2不需要被淘汰嘛？

因为根本不需要这样，5*2也等于2*5，在发现2是质数的时候，他早就被筛选掉了！

上一篇
下一篇