求质数表2——线性筛法

合数的标准分解

每个合数可以分解质因数,对于 60,最小质因子(LPF)为 2,最大质因子(GPF)为 5。 根据 LPF 和 GPF,可以将 60 分解为 2 * 30 或 5 * 12。这里的 30 为 LPF 的补,12 为GPF的补。

欧拉筛

对于 60 之前的埃氏筛法最大的问题就是在 2、3、5 都会划去一次,浪费了很多时间。欧拉筛的改进方法就是保证每个合数只被划掉一次。 枚举最小质因子(LPF),把它与未筛掉的各数相乘,筛掉乘积。 那怎么找到未筛掉的数呢?我们不能再用一个 bool 数组来保存是否被筛掉了,因为那样你依然是在遍历数组看看那个数是否被划掉,如果没有的话就将它与最小质因子的积划掉。这样还是遍历了所有的数,我们只想要遍历没有被划掉的数。 我们需要一个数据结构可以高效的进行遍历、查找、删除操作。链表的遍历和删除都可以满足我们的需求,但查找过慢。 我们用数组模拟链表来保证这三个操作的高效。

1
2
3
4
5
6
7
8
9
10
int prev[MAX_N + 2];	//保存每个节点的前一个节点的值
int next[MAX_N + 2]; //保存每个节点的后一个节点的值

for( int i = 2; i <= N; i++){ //初始化
prev[i] = i - 1;
prev[i] = i + 1;
}

next[prev[x]] = next[x];
prev[next[x]] = prev[x]; //删除 x 节点的操作

数组模拟的链表的实现及相关操作
解决“链表”问题后,我们在埃氏筛法的基础上改进划掉的操作就可以。

代码

Ubuntu Pastebin : https://paste.ubuntu.com/p/CCWTJHjSYJ/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int prev[MAX_N + 2];
int next[MAX_N + 2];

int euler(int N)
{
for( int i = 2; i <= N; i++){
prev[i] = i - 1;
prev[i] = i + 1;
}
int nPrimes = 0;

for( int p = 2; p * p <= N; p = next[p]){
for( int f = p; p * f <= N; f = next[f]){
int x = p * f;
next[prev[x]] = next[x];
prev[next[x]] = prev[x];
}
}

for( int p = 2; p <= N; p = next[p]){
primes[nPrimes++] = p;
}
return nPrimes;
}

但此代码有个大BUG,因为我们在选定一个 p 时想划去的是当时在它之后没有被划掉的数与它的积,但选定 p 是在找没有被划掉的数之前的。会发生这样的事情,比如我们 p 为 2,我们划掉了 4,那我们就没办法通过 2 * 4 划掉 8。 为了解决这个问题,人们想出了两种解决方案。

  • 第一种:从大到小的去划掉需要划掉的数,这个方案需要解决的问题是需要定位链表的最后一个节点。
  • 第二种:为什么 8 不能通过 2 * 4 划掉,因为 8 存在多个质因子为 2,所以我们在划去p * f时,可以顺便划掉p * p * f,p * p * p * f…… 解决。

    第一种

    Ubuntu Pastebin : https://paste.ubuntu.com/p/4cPKvKw6ys/

    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
    28
    int prev[MAX_N + 2];
    int next[MAX_N + 2];

    int euler(int N)
    {
    for( int i = 2; i <= N; i++){
    prev[i] = i - 1;
    prev[i] = i + 1;
    }
    int nPrimes = 0;

    for( int p = 2; p * p <= N; p = next[p]){
    primes[nPrimes++] = p;

    int f = p;
    while(p * next[f] <= N){ //遍历链表找到最大的f
    f = next[f];
    }

    while(f >= p){ //反向遍历链表划去p * f
    int x = p * f;
    next[prev[x]] = next[x];
    prev[next[x]] = prev[x];
    f = prev[f];
    }
    }
    return nPrimes;
    }

第二种

Ubuntu Pastebin :https://paste.ubuntu.com/p/rnjmh7vTPF/

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
int prev[MAX_N + 2];
int next[MAX_N + 2];

int euler(int N)
{
for( int i = 2; i <= N; i++){
prev[i] = i - 1;
prev[i] = i + 1;
}
int nPrimes = 0;

for( int p = 2; p * p <= N; p = next[p]){
for( int f = p; p * f <= N; f = next[f]){
for( int x = p * f; ; x *= p){
next[prev[x]] = next[x];
prev[next[x]] = prev[x];
if(x > N / p) break; //x增长较快,防止x溢出
}
}
}

for( int p = 2; p <= N; p = next[p]){
primes[nPrimes++] = p;
}
return nPrimes;
}

时间复杂度

每个数只被划掉一次所以是 \(O(N)\)。但划掉的速度要通过链表,其实导致速度通常还不如埃氏筛法

空间复杂度

只开了两个链表的数组和一个primes数组,\(O(N)\)。

简易欧拉筛

再考虑欧拉筛的缺点,它时间复杂度已经达到线性,但链表操作太慢。怎么可以不使用链表实现欧拉筛呢? 我们为什么要用到链表?因为 f 是动态变化的。我们换一种方式,考虑枚举LPF的补也就是先枚举 p (从质数表 primes 数组中取即可)再枚举 f 。根据LPF的定义我们给定 p 后,f 只需枚举到第一个整除 p 的数。

代码

Ubuntu Pastebin : https://paste.ubuntu.com/p/xfVS3ctQWr/

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
bool flag[MAX_N + 1];

int simple_euler(int N)
{
memset(flag, true, (N + 1) * sizeof(bool));
int nPrimes = 0;
for( int f = 2; f <= N / 2; f++){
if(flag[f]){
primes[nPrimes++] = f;
}
for( int u = 0; u < nPrimes; u++){
int p = primes[u];
if(p * f > N) break;
flag[p * f] = false;
if(f % p == 0) break;
}
}

for( int i = N / 2 + 1; i <= N; i++){
if(flag[i]){
primes[nPrimes++] = i;
}
}
return nPrimes;
}

时间复杂度

依然是 \(O(N)\),但没有了复杂操作,效率优于之前的埃氏筛和枚举LPF的欧拉筛。 空间复杂度: \(O(N)\) 与欧拉筛相同。

本文标题:求质数表2——线性筛法

文章作者:赵砚潇

发布时间:2018年03月09日 - 10:03

最后更新:2018年07月26日 - 19:07

原始链接:https://blog.zyx.sh/2018/03/09/isprimes-2/

许可协议: 署名-非商业性使用-相同方式分享 4.0 国际 转载请保留原文链接及作者。

Donate comment here