Fork me on GitHub

埃拉托斯特尼筛法

发表于 | 分类于
字数统计: 1,362 | 阅读时长 ≈ 5
什么是埃拉托斯特尼筛法

简称埃氏筛，是一种简单且年代久远的筛法，用来找出一定范围内所有的素数。

所使用的原理是从2开始，将每个素数的各个倍数，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以素数来测试每个待测数能否被整除。

算式

给出要筛数值的范围n，找出 {\displaystyle {\sqrt {n}}} \sqrt{n}以内的素数 {\displaystyle p{1},p{2},\dots ,p{k}} p1,p2,\dots ,p。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去……。

步骤

找出25以内的所有素数，详细列出算法如下：

  1. 列出2以后的所有序列：
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

  2. 标出序列中的第一个质数，也就是2，序列变成：
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

  3. 将剩下序列中，划摽2的倍数（粗体），序列变成：
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
    如果现在这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是质数，否则回到第二步。

  1. 本例中，因为25大于2的平方，我们返回第二步： 剩下的序列中第一个质数是3，将主序列中3的倍数划出，主序列变成：
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
    我们得到的质数有：2，3

  1. 25仍然大于3的平方，所以我们还要返回第二步： 现在序列中第一个质数是5，同样将序列中5的倍数划出，主序列成了：
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
    我们得到的质数有：2 3 5 。

  2. 因为25等于5的平方，跳出循环. 结论：去掉划出的数字，2到25之间的质数是：2 3 5 7 11 13 17 19 23。

图解

这里写图片描述

c++代码

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 <vector>
#include <algorithm>//std::remove_if
#include <numeric>//std::iota
std::vector<int> eratosthenes(int max){
  std::vector<int> vi(max+1);//0, 1, 2, ..., max
  std::iota(vi.begin(), vi.end(), 0);
  if(max>=2){
    int prime=2;
    while(prime*prime<=max){//2 to sqrt(max)
      for(size_t index=prime*2; index<vi.size(); index+=prime){
        vi[index]=0;//Rule out this number.
      }
      for(prime++; prime*prime<=max; prime++){
        if(vi[prime]>0){
          break;//Jump to next non-zero.
        }
      }
    }
  }
  vi.erase(std::remove_if(vi.begin(), vi.end(), [](int i)->bool{
    return i<=1;
  }), vi.end());//Remove all zeros and the one.
  return vi;
}

以上是来自维基百科的说法。

其实就是直接构造一个整型的数组，经过埃氏筛之后把合数置为0，对于一般占4个字节的int来说，每一个数不管素数还是合数都要占据4个字节的空间，但其实我是不需要合数的，当n很大的时候空间开销就会特别大。

另一种方法就是筛的时候遇到合数就将它删掉，这样最后数组内只剩下素数，看起来不错可以减少空间的开销，但是频繁地对一个大的容器进行删除操作可能会导致频繁的内存分配和释放，而频繁的内存分配/释放，会导致明显的 CPU 占用并可能造成内存碎片。

优化
按布尔（bool）存储的思路。
构造一个定长的布尔型容器（通常用数组）。比方说，质数的分布范围是1,000,000，那么就构造一个包含1,000,000个布尔值的数组。然后把所有元素都初始化为 true。在筛的过程中，一旦发现某个自然数是合数，就以该自然数为下标，把对应的布尔值改为 false。
全部筛完之后，遍历数组，找到那些值为 true 的元素，把他们的下标打印出来即可。此种境界的好处在于：其一，由于容器是定长的，运算过程中避免了频繁的内存分配/释放；其二，在某些语言中，布尔型占用的空间比整型要小。比如 C++ 的 bool 仅用1字节
　　注：C++ 标准（ISO/IEC 14882）【没有】硬性规定 sizeof(bool)==1，但大多数编译器都实现为单字节。

继续优化
按位（bit）存储的思路。
以 C++ 为例。一个 bool 占用1字节内存。而1个字节有8个比特，每个比特可以表示0或1。所以，当你使用按位存储的方式，一个字节可以拿来当8个布尔型使用。所以，达到此境界的程序猿，会构造一个定长的 byte 数组，数组的每个 byte 存储8个布尔值。空间性能相比境界2，提高8倍（对于 C++ 而言）。如果某种语言使用4字节表示布尔型，那么境界3比境界2，空间利用率提高32倍。

当然，楼上的方法并不一定是最优的方法。欢迎各位挑刺。

undefined