前言
素数是一个正整数,只能除以 1 和自身,不包括 1。几个世纪以来,这种类型的数字因其在各种数学概念(包括密码学和数论)中的独特性质和重要性而使数学家着迷。此外,素数在数学之外还有实际应用,例如在计算算法和数据编码中。然而,识别素数可能是一项具有挑战性的任务,特别是对于大数,并且正在研究寻找有效的素数生成和测试方法。尽管困难重重,素数仍然是数学的一个迷人而基本的方面,还有许多迷人的性质有待发现。
为了判断一个数是否为素数,除了使用这个定义法,还有更多复杂度较小的算法,这些算法也被称作素数筛,该文即是来介绍不同素数筛算法的。
定义法
优化前
因为素数是只能被自身与1整除的数字,那么我们就可以判断这个数字能否被比它小的数字整除,这是一个十分简单粗暴的方法,如果要列出前n个正整数中的素数,时间复杂度达到了惊人的O(n²)
#include <bits/stdc++.h> using namespace std; bool isPrime(int num) { if (num == 2) return true; for (int i = 2; i < num; i++) { if (num % i == 0)return false; } return true; } void outPrime(int arrange) { for (int i = 2; i <= arrange; i++) { if (isPrime(i)) cout << i << endl; } } int main() { outPrime(100); }
这一段代码可以输出前1~100之间的素数,但是一旦这个范围达到1~1000000就会导致要等待很长一段时间才能出结果,因为他的复杂度是O(n²)。
优化后
在判断n是否为素数时,实际上我们不必让n取模循环到n-1,根据已知数学知识,我们可以只用循环到sqrt(n)即可,于是整段代码的时间复杂度变为O(nlogn)
#include <bits/stdc++.h> using namespace std; bool isPrime(int num) { if (num == 2) return true; for (int i = 2; i * i < num; i++) { if (num % i == 0)return false; } return true; } void outPrime(int arrange) { int temp = 0; for (int i = 2; i <= arrange; i++) { if (isPrime(i)) cout << i << endl; } } int main() { outPrime(1000000); }
这串代码耗时就比优化前要快很多,当然,为了更快的得到素数表,仍然有时间复杂度更小的算法,下面我们来介绍素数筛。
素数筛
埃氏筛
举个例子,我们先列出2~16(1不是素数):
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
然后从2开始,将所选数字的所有倍数标红
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
接着下一个素数是3
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
下一个素数是5,但是5 * 5 > 16,超出了这一串数字的上限,所以不需要继续往后面处理了。
于是颜色仍然是黑色的就是素数。
#define MAXN 1000 #include <bits/stdc++.h> using namespace std; int main() { int isPrime[1001] = {0}; // 若为素数则是1 memset(isPrime, 1, sizeof(isPrime)); for (int i = 2; i * i <= MAXN; i++) { if (isPrime[i]) { for (int j = 2; i * j <= MAXN; j++) { isPrime[i * j] = 0; // 为倍数则不是素数 } } } for (int i = 2; i <= MAXN; i++) { if (isPrime[i]) { cout << i << endl; } } }
代码实现过程如上,可以输出1~1000以内的素数,其复杂度是O(n)=nloglogn。
但是我们能注意到,一个数可以是不同素数的倍数,比如说15 = 3 * 5,那么循环到3和5的时候都会对15进行一次筛选操作,于是会进行一次重复无效操作,那么我们引入了欧拉筛这一算法,这个算法的本质是让合数被它的最小质因数筛选掉。
欧拉筛
再次引入1~16
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Primes = [2]
让2与Primes里的元素求积,2*2=4,所以将4标红
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Primes = [2,3]
让3与Primes里的元素求积,3*2 = 6,3*3 = 9,所以将6和9标红
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Primes = [2,3]
让4与Primes里的元素求积,4*2 = 8,4*3 = 12,将8和12标红
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Primes = [2,3,5]
以此类推,10、15、25标红,因为25>16,所以跳过
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Primes = [2,3,5]
最后循环到8就可以将所有合数筛掉
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
因为任意合数都能拆成一个素数乘一个整数,所以我们只需要找出这个最小的素数即可。
#include <bits/stdc++.h> #define MAXN 100000000 using namespace std; int isPrime[100000000]; int main() { vector<int> primes; memset(isPrime, 1, sizeof(isPrime)); // 质数为1,筛掉合数为0 for (int i = 2; i <= MAXN; i++) { if (isPrime[i]) { primes.push_back(i); } for (int j : primes) { if (i * j > MAXN)break; isPrime[i * j] = 0; } } for (int num : primes) { cout << num << endl; } }
该代码的时间复杂度只有O(n)=n,如果把底下的输出语句删掉,该代码获得1~1e之间的素数只要2~3s,巨快!