素数线性筛

素数打表是编程中常遇到的一个问题

一个简单的筛法

思路就是筛去已有素数的倍数,用一个数组来标记合数

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
#include<iostream>
#include<ctime>
using namespace std;
const int N = 1000000;
bool check[N] = { 0 };
int prime[N] = { 0 };
int main(void)
{
int pos = 0;
for (int i = 2; i < N; i++)
{
//如果没有标记过,便添加到素数表
if (!check[i])
prime[pos++] = i;
//筛掉当前数的倍数
for (int j = 2 * i; j < N; j += i)
{
check[j] = true;
}
}
cout << (double)clock() / CLOCKS_PER_SEC;
return 0;
}

此筛法的时间复杂度为\(O(NloglogN)\)

空间复杂度为\(O(N)\)

这里还要提到几点,
一是在开pirme数组时可以预估一下素数的个数大约为\(N/lnN\)。
二是对于比较大的N,栈空间可能不够用,建议开在堆上。
三是此算法有较多的重复计算还可以改进,改进见后文。

高效线性筛

在前文提到的筛法中我们发现有很多重复的筛,比如6可以被23筛掉也可以被32筛掉,为了解决这个问题,就要提到高效线性筛法

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
27
#include<iostream>
#include<ctime>
using namespace std;
const int N = 1000000;
bool check[N] = { 0 };
int prime[N] = { 0 };
int main(void)
{
int pos = 0;
for (int i = 2; i < N; i++)
{
if (!check[i])
prime[pos++] = i;
for (int j = 0; j < pos&&i*prime[j] < N; j++)
{
check[i*prime[j]] = true;
if (i%prime[j] == 0)//最为关键的一步
break;
//避免了很多的重复判断,比如i=9,现在素数是2,3,5,7,进入二重循环,check[2*9]=1;check[3*9]=1;这个时候9%3==0,要跳出。因为5*9可以用3*15来代替,如果这个时候计算了,i=15的时候又会被重复计算一次,所以这里大量避免了重复运算。
}
}
cout << (double)clock() / CLOCKS_PER_SEC;
return 0;
}
//prime[]数组中的素数是递增的,当i能整除prime[j],那么i*prime[j+1]这个合数肯定被prime[j]乘以某个数筛掉。
因为i中含有prime[j],prime[j]比prime[j+1]小,即i=k*prime[j],那么i*prime[j+1]=(k*prime[j])*prime[j+1]=k’*prime[j],接下去的素数同理。所以不用筛下去了。
因此,在满足i%prime[j]==0这个条件之前以及第一次满足改条件时,prime[j]必定是prime[j]*i的最小因子。

这种算法的效率几乎能到\(O(N)\)