线性筛质数-欧拉筛-python-c++

想要快速地筛出一定上限内的素数？

下面这种方法可以保证范围内的每个合数都被删掉（在 bool 数组里面标记为非素数），而且任一合数只被：

“最小质因数 × 最大因数（非自己） = 这个合数”

的途径删掉。由于每个数只被筛一次，时间复杂度为 O(n)。

欧拉筛

先浏览如何实现再讲其中的原理。

实现

#include 
#include bool isPrime[100000010];
//isPrime[i] == 1表示：i是素数
int Prime[6000010], cnt = 0;
//Prime存质数void GetPrime(int n)//筛到n
{memset(isPrime, 1, sizeof(isPrime));//以“每个数都是素数”为初始状态，逐个删去isPrime[1] = 0;//1不是素数for(int i = 2; i <= n; i++){if(isPrime[i])//没筛掉 Prime[++cnt] = i; //i成为下一个素数for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) {//从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数//当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的isPrime[i*Prime[j]] = 0;if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子break; //重要步骤。见原理}}
}int main()
{int n, q;scanf("%d %d", &n, &q);GetPrime(n);while (q--){int k;scanf("%d", &k);printf("%d\n", Prime[k]);}return 0;
}

import time
def get_prime(x):for i in range(2,x+1):if st[i]:primes.append(i)for j in range(len(primes)):if primes[j]*i>x:breakst[primes[j]*i]=Falseif i%primes[j]==0:break
start=time.time()
n=10000
N=n+5
st=[True]*N
primes=[]
get_prime(n)
print(len(primes))
end=time.time()
print('程序运行时间',end-start)
with open('./primes.txt','w') as f:f.write('\n'.join(map(str,primes)))

原理概述

代码中，外层枚举i=1→n。对于一个 ii，经过前面的腥风血雨，如果它还没有被筛掉，就加到质数数组 Prime[]中。下一步，是用 i来筛掉一波数。

内层从小到大枚举 Prime[j]。i×Prime[j] 是尝试筛掉的某个合数，其中，我们期望 Prime[j] 是这个合数的最小质因数 (这是线性复杂度的条件，下面叫做“筛条件”)。它是怎么得到保证的？

j 的循环中，有一句就做到了这一点：

if(i % Prime[j] == 0)break; 

j 循环到 i \mod Prime[j] == 0imodPrime[j]==0 就恰好需要停止的理由是：

下面用 s(smaller) 表示小于 j 的数，L(larger)表示大于 j 的数。

① i 的最小质因数肯定是 Prime[j]。

（如果 i 的最小质因数是 Prime[s] ，那么 Prime[s] 更早被枚举到（因为我们从小到大枚举质数），当时就要break）

既然 ii 的最小质因数是 Prime[j]，那么 i×Prime[j] 的最小质因数也是 Prime[j]。所以，j 本身是符合“筛条件”的。

②i×Prime[s] 的最小质因数确实是 Prime[s]。

（如果是它的最小质因数是更小的质数 Prime[t]，那么当然Prime[t] 更早被枚举到，当时就要break）

这说明 j 之前（用 i×Prime[s] 的方式去筛合数，使用的是最小质因数）都符合“筛条件”。

③ i × Prime[L] 的最小质因数一定是 Prime[j]。

（因为 i 的最小质因数是 Prime[j]，所以 i×Prime[L] 也含有 Prime[j] 这个因数（这是 i 的功劳），所以其最小质因数也是 Prime[j]（新的质因数 Prime[L] 太大了））

这说明，如果 j 继续递增（将以 i×Prime[L] 的方式去筛合数，没有使用最小质因数），是不符合“筛条件”的。

小提示：

当 ii 还不大的时候，可能会一层内就筛去大量合数，看上去耗时比较大，但是由于保证了筛去的合数日后将不会再被筛（总共只筛一次），复杂度是线性的。到 ii 接近 nn 时，每层几乎都不用做什么事。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！