筛质数
csdn地址:https://blog.csdn.net/duchenlong/article/details/112141898
时间复杂度$O(n \log n)$
$\frac{n}{2} + \frac{n}{3}+… + \frac{n}{n}$
$\Rightarrow$ $n\times (\frac{1}{2} + \frac{1}{3}+… + \frac{1}{n})$(调和级数)
$\Rightarrow$ $n \times (\ln n + C)$
$\Rightarrow$ $n \times \ln n$
$\Rightarrow$ $n \times \log_e n$ $< n \times \log_2 n$
void get_prime() {
int cnt = 0;
for(int i = 2; i <= n; i++) {
if(f[i] == 0)
cnt ++;
// 标记 i 的倍数
for(int j = i; j <= n; j += i)
f[j] = 1;
}
printf("%d\n",cnt);
}
但实际上,对于不是质数的数,我们没有必要进入循环判断,所以可以优化一下
这样的时间复杂度为$O(n \log\log n)$(埃拉托斯特尼筛法)
用质数就把所有的合数都筛掉
$1\rightarrow n$有$\frac{n}{ln n}$个质数,时间复杂度近似为$O(n \log\log n)$
什么概念呢,当$n=2 ^ {32}$时,$O(n \log\log n) = 5$
void get_prime() {
int cnt = 0;
for(int i = 2; i <= n; i++) {
if(f[i]) continue;
cnt ++;
// 标记 i 的倍数
for(int j = i; j <= n; j += i)
f[j] = 1;
}
printf("%d\n",cnt);
}
线性筛选
$n$只会被自己的最小质因子筛选掉
i % prime[j] == 0
,$prime[j]$定为$i$最小质因子,$prime[j]$也定为$prime[j] \times i$最小质因子i % prime[j] != 0
,$prime[j]$定小于$i$的所有质因子,所以$prime[j]$也为$prime[j] \times i$最小质因子
每一次向前标记的过程中,都是只遍历到自己的第一个质因子为止,因为标记的过程是在判断之前,所以保证了一定使用了最小质因子对下一个合数进行了标记。
极大减少了重复标记的次数
比如说在埃氏筛选中,$6$会被 2 和 3进行标记,这就发生了重复标记。
而线性筛选就避免了这一情况
void get_prime() {
int cnt = 0;
for(int i = 2; i <= n; i++) {
if(!f[i]) prime[cnt ++] = i;
// 线性筛选,枚举所有的质数
for(int j = 0; prime[j] <= n / i; j++) {
f[prime[j] * i] = 1;
if(i % prime[j] == 0) //prime[j]一定是i的最小质因子
break;
}
}
printf("%d\n",cnt);
}
在$n=10^7$时,线性筛选法大概会比埃氏筛选法快一倍