Problem6566--学习系列 —— 埃拉托斯特尼筛

6566: 学习系列 —— 埃拉托斯特尼筛

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 0Submit Num: 0StatisticsShowOff!

Description

【知识点】

如果我们想要知道小于等于 $n$ 有多少个素数呢？
一个自然的想法是对于小于等于 $n$ 的每个数进行一次质数检验。这种暴力的做法显然不能达到最优复杂度。
埃拉托斯特尼筛法，简称埃筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数 $n$ 以内的全部素数，必须把不大于根号 $n$ 的所有素数的倍数剔除，剩下的就是素数。
用筛法求素数的基本思想是：
把从 $2$ 到 $N$ 的一组正整数从小到大按顺序排列。从中依次删除 $2$ 的倍数、$3$ 的倍数、$5$ 的倍数，直到 $\sqrt{N}$ 的倍数为止，剩余的即为 $2 \sim N$ 之间的所有素数。
下面我们从 $2 \sim 30$ 筛出所有素数。
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
去掉 $2$ 的倍数（不包括 $2$ ）4 6 8 10 12 14 16 18 20 22 24 26 28 30，余下的数是：
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
剩下的数中 $3$ 最小，去掉 $3$ 的倍数 6 9 12 15 18 21 24 27 30，余下的数是：
2 3 5 7 9 11 13 17 19 23 25 27 29
剩下的数中 $5$ 最小，去掉 $5$ 的倍数 10 15 20 25 30，余下的数是：
2 3 5 7 9 11 13 17 19 23 27 29
剩下的数中 $7$ 最小，去掉 $7$ 的倍数 14 21 28，余下的数是：
2 3 5 7 9 11 13 17 19 23 27 29
其实，我们已经发现剩余的数字中，已经没有 $7$ 的倍数了。
如此下去直到所有的数都被筛完，求出的素数为：
2 3 5 7 11 13 17 19 23 29


具体过程可以看下面的动画。


【时间复杂度】

如果每一次对数组的操作花费 $1$ 个单位时间，则时间复杂度为：$O\left(n\sum_{k=1}^{\pi(n)}{1\over p_k}\right)$，其中 $p_k$ 表示第 $k$ 小的素数。根据 Mertens 第二定理，存在常数 $B_1$ 使得：
$$\sum_{k=1}^{\pi(n)}{1\over p_k}=\log\log n+B_1+O\left(1\over\log n\right)$$
所以 Eratosthenes 筛法 的时间复杂度为 $O(nloglogn)$

Input

【代码】 

const int N=1e7+10;
bool prime[N]; 
/*
*prime[i]=false表示数字i为素数，true表示数字i为素数
*这里我们利用了全局变量初始化都是0这个特点
*/

void Eratosthenes(int n) {
    prime[0]=prime[1]=true;//数字0,1不是素数
    for (int i=2; i*i<=n; i++) {//注意这里 i*i 优化
        if (prime[i]==false) {
            //i是质数，将所有i的倍数设置为不是素数
            for (int j=i*i; j<=n; j+=i) {
                prime[j]=true;//j不是素数
            }
        }
    }
}

Source/Category

 
Submit