质数,也叫素数。作为自然界的神奇规律,在数学、物理、计算机等学科有着重要的地位。本篇文章将讨论计算机筛素数的三种经典算法。
朴素法
首先我们介绍朴素法。根据质数的定义,质数是指在大于 $1$ 的自然数中,除了1和它本身以外不再有其他因数的自然数。因此我们只需要一个一个判断,如果确实没有其他的因数,就是质数了。这就是判断质数的代码,十分暴力。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| #include <stdio.h> bool isprime(int n) { if(n <= 1) return false; for(int i=2; i<=n; ++i) { if(n % i == 0) return false; } return true; } int main() { for(int i=1; i<=100; ++i) { if(isprime(i)) printf("%d ", i); } return 0; }
|
在这段代码中,有一个地方可以优化,那就是 $i$ 不一定非要从 $2$ 循环到 $n$ ,只需要循环到根号 $n$ 就行了。因为 $n$ 的因子除了根号 $n$ ,必然有一个大于根号 $n$ ,一个小于根号 $n$ ,如果没有发现小于根号 $n$ 的那个,也就必然不会再发现大于根号 $n$ 的那个了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| #include <stdio.h> bool isprime(int n) { if(n <= 1) return false; for(int i=2; i*i<=n; ++i) { if(n % i == 0) return false; } return true; } int main() { for(int i=1; i<=100; ++i) { if(isprime(i)) printf("%d ", i); } return 0; }
|
埃氏筛
接下来我们介绍埃氏筛法。那么我们既然已经有了朴素法,为什么还要学习埃氏筛法呢?那就是因为朴素法慢,求 $n$ 以内质数需要 $O(n\sqrt{n})$ 的时间复杂度。接下来我们学习一个时间复杂度为 $O(n\log{\log{n}})$ 的算法,埃氏筛算法。考虑合数的特征,一定存在两个除了1和它本身之外的因子,我们只需要从前往后把所有质数的倍数筛掉就行了。例如刚开始我们知道 $2$ 是质数,那么我们就把 $4, 6, 8, 10, 12 …$ 筛掉,然后我们知道 $3$ 是质数,就把 $6, 9, 12, …$ 筛掉,这样留下来没被筛掉的数就是质数了。这就是埃氏筛的代码,可以证明,它的时间复杂度是$O(n\log{\log{n}})$ ,当n很大时比朴素法有更大的优势。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| #include <stdio.h> #define MAXN (1000005) int prime[MAXN]; bool isprime[MAXN]; int sieve(int n) { int p=0; for(int i=0; i<=n; ++i) isprime[i]=true; isprime[0]=isprime[1]=false; for(int i=2; i<=n; ++i) { if(isprime[i]) { prime[p++]=i; for(int j=2; j*i<=n; ++j) isprime[j*i]=false; } } return p; } int main() { int n = sieve(100); for(int i=0; i<n; ++i) { printf("%d ", prime[i]); } }
|
欧拉筛
最后,我们介绍欧拉筛,既然已经有这么优秀的埃氏筛,为什么还要学习欧拉筛呢?不妨观察,刚才筛 $2$ 的倍数和 $3$ 的倍数时,它们筛掉了很多共同的数,如 $6, 12, …$ 而这是没有必要的,每个数其实筛一次就够了。我们先写出来被筛掉的合数,观察一下,看看能不能发现什么规律。我们发现,从右向左看,每列的被乘数都是从 $2$ 开始的质数;从上至下看,每行的乘数都会逐渐增大,直到被乘数能整除乘数为止。所以算法的思路就很明确了,只需要用一个循环变量 $i$ ,如果 $i$ 没有被筛掉就把 $i$ 加入质数表,并筛掉质数表中现有的质数与 $i$ 的乘积,当被乘数整除乘数时, $i$ 自增 $1$ 。这就是欧拉筛的代码,虽然较为复杂,但算法效率高,复杂度是线性的。
1 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
| #include <stdio.h> #define MAXN (1000005) int prime[MAXN]; int isprime[MAXN]; int sieve(int n) { int p=0; for(int i=0; i<=n; ++i) isprime[i]=true; isprime[0]=isprime[1]=false; for(int i=2; i<=n; ++i) { if(isprime[i]) { prime[p++] = i; } for(int j=0; j<p; ++j) { if(prime[j]*i > n) break; isprime[prime[j]*i] = false; if(i % prime[j] == 0) break; } } return p; } int main() { int n = sieve(100); for(int i=0; i<n; ++i) { printf("%d ", prime[i]); } }
|