打印素数: 埃筛与线筛

埃氏筛法

题目

https://www.luogu.com.cn/problem/P3912

算法

这道题的数据太大, 普通穷举一定会超时.

使用筛选法, 找到根号N内的素数, 找到一个素数就把素数的倍数筛去, 然后找到下一个素数再筛去倍数.

算法动图:

根据算法写出代码 :

#include <bits/stdc++.h>
using namespace std;
const int UBOUND = 100;
bool flag[UBOUND];
int main(){
    int lim = sqrt(UBOUND);
    flag[0] = flag[1] = false;      // 0 和 1 不是质数
    memset(flag,true,sizeof(flag));
    for(int i=2;i<=lim;i++){        // 优化: 循环到平方根即可
        if(flag[i])
            for(int j=i*i;j<=UBOUND;j+=i)   // 优化
                flag[j]=false;
    } 
    for(int i=0;i<=UBOUND;i++)
        if(flag[i])
            cout<<i<<" ";
    return 0;
}

以上用 flag[i] 去存 i 是否是质数, true 表示质数.
在提交的时候肯定不会写 memset 语句, 直接反过来 false 代表质数就可以了.

为什么是从 i*i 开始而不是从 2i 开始, 其实很好理解, 因为每个 i*p (p<=i-1) 都已经被 p 的序列筛选过了. 比如 i*(i-1) 已经被 (i-1)*(i-1) 筛选过了, 所以无需重复筛选.

代码:

附带练习

http://noi.openjudge.cn/ch0105/44/

线性筛法

之前讲过的埃筛还是不算太快, 因为会有重复筛选. 比如说 30 会被 2、3、5 重复筛掉. 线性筛法就是为了这个发明出来, 保证每个数都会被筛到且每个数只筛一遍.

题目

https://www.luogu.com.cn/problem/P3383

算法

如果用之前的埃氏筛法做这题, 一定会超时, 原因还是某些数字被重复筛掉了.

线性筛法见以下代码:

#include <iostream>
using namespace std;

const long long int UBOUND = 100000000;
bool f[MAXN];
long long int p[UBOUND], pos = 0;

int main() {
  f[0]=f[1]=true;
  for (long long int i = 2; i <= UBOUND; i++) {
    if (!f[i])
      p[pos++] = i;

// # 断点 1

    for (long long int j = 0; j < pos && i * p[j] <= UBOUND; j++) {
      // 这个循环是算质因数的乘积, 乘积就是要被筛掉的数
      // 因为一切合数都可以表达为几个质因数的乘积
      // 也就是说, i 是系数, 被排除的合数 = i*p[j]
      f[p[j] * i] = true;

// # 断点 2

      if (i % p[j] == 0) //  若 i 含有质因数就不用再乘一次, 否则造成重复
        break;
    }
  }

  for (long long int i = 0; i<pos; i++)
    cout << p[i] << " ";
  return 0;
}

原理:

任何合数都可以表达为一系列质数的乘积.

#1 下面的那个循环条件为 j<pos && i*p<=UBOUND, 第一个条件保证了取到的 pos[j] 这个质数一定要比当前的 i 要小 (无论 i 是质数还是合数!); 第二个条件保证了要排除的合数在范围内.

执行到 #1, 如果 i 是质数, 那么被筛出的数 = i * 比 i 小的质数, 因为 i 是唯一的, 所以算出来的结果不会重复.

如果 i 是合数, 此时 i 可以表达为一系列递增质数 p1*p2*p3*...*pn 的乘积, p1 最小. #2 下面的 break 语句保证了只能筛出 不大于 p1 的质数 * i.

比如说, i = 2*3*5, break 语句保证了只能筛出 2i 而不是 3i, 不然就和之后被筛出的 i = 3*3*5 , i*2 重复了.

讲到这里, 差不多对线筛就有一个印象了. 具体怎么证是数论的问题, 我不打算在这篇博文里把它彻底弄懂, 只要会用就可以了. 如果想要证明为什么这种筛法保证了无重复、都筛到, 可以参考这篇文章. (上文的很多地方也是我从这篇文章摘抄下来的)

Tips

不要预定义

提交代码的时候, 连续碰到编译错误:

最后发现碰上好一个大坑:
一开始初始化 f 的代码是这样的:

bool f[MAXN]={1,1};

看评论区后得知, 这样写相当于在编译的时候就为数组分配好了空间, 而不是在执行的时候动态分配, 所以导致文件过大的错误.

改正之后全部 AC, nice.

BitSet

bool 数组的空间开销很大, 将以下这句

bool f[MAXN];

改为

bitset<MAXN> f;

即可. 需要包含 #include <bitset> 头文件 (已经包含在万能头文件里面) , 其余不用变更任何东西, 即可轻轻松松节省空间为原来的 1/3 !

(但是 bitset 在节省空间的同时会增加时间开销, 用不用是见仁见智的问题. 这道题我用不用都可以过, 所以也无所谓了. 因为只是实验算法, 如果真的碰到最好加上手动输入输出可以大大优化时间. )

代码:

参考

• 维基百科: 埃拉托斯特尼筛法
• 知乎: 关于从埃氏筛到线性筛你不会想知道的那些事
• CSDN: 一般筛法求素数+快速线性筛法求素数
• 洛谷: 「编译错误」讨论串