筛法求素数

一般的线性筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void make_prime()
{
memset(prime, 1, sizeof(prime));
prime[0] = false;
prime[1] = false;
int N = 31700;
for(int i=2; i<N; i++)
{
if(prime[i])
{
prime[++cnt] = i;
for(int k = i*i; k<N; k+=i)
{
prime[k] = false;
}
}
}
return;
}

初始时,假设全部都是素数,当找到一个素数时,显然这个素数乘上另外一个数之后都是合数(注意上面的 ii , 比 i2 要快点 ),把这些合数都筛掉

但仔细分析能发现,这种方法会造成重复筛除合数,影响效率。比如10,在i=2的时候,k=215筛了一次;在i=5,k=56 的时候又筛了一次。所以,也就有了快速线性筛法。

快速线性筛法

快速线性筛法没有冗余,不会重复筛除一个数,所以“几乎”是线性的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
const long N = 200000;
long prime[N] = {0}, num_prime = 0;
int isNotPrime[N] = {1, 1};

int main()
{
for(long i = 2; i < N; i++)
{
if(!isNotPrime[i])
prime[num_prime++] = i;
for(long j = 0; j < num_prime && i * prime[j] < N; j++)
{
isNotPrime[i*prime[j]] = 1;
if(!(i % prime[j]))
break;
}
}
return 0;
}

任何合数都能表示成一系列素数的积

不管 i 是否是素数,都会执行到“关键处1”,

①如果 i 都是是素数的话,那简单,一个大的素数 i 乘以不大于 i 的素数,这样筛除的数跟之前的是不会重复的。筛出的数都是 N=p1*p2的形式, p1,p2之间不相等

②如果 i 是合数,此时 i 可以表示成递增素数相乘 i=p1p2…*pn, pi都是素数(2<=i<=n), pi<=pj ( i<=j )

p1是最小的系数。

根据“关键处2”的定义,当p1==prime[j] 的时候,筛除就终止了,也就是说,只能筛出不大于p1的质数*i。

我们可以直观地举个例子。i=235

此时能筛除 2i ,不能筛除 3i

如果能筛除3i 的话,当 i’ 等于 i’=335 时,筛除2i’ 就和前面重复了。

Donate? comment?