检定素数的算法:埃氏筛(埃拉托斯特尼筛法)、欧拉筛(线性筛)

埃氏筛

时间复杂度:$O(n\log\log n)$

代码实现:

// isprime储存该数是否为素数
bool isprime[SIZE];
memset(isprime, true, sizeof(isprime));
// 特判0、1不是素数
isprime[0] = isprime[1] = false;
// 使用埃氏筛处理>1的情况
for (int i = 2; i < SIZE; i++)
{
    if (isprime[i])
    {
        for (int j = 2; j * i < SIZE; j++)
        {
            isprime[i * j] = false;
        }
    }
}

算法结果:

得到一个范围从 0 到 SIZE 的 bool 数组 isprime,每一位储存该数字是否是素数。

算法思路:

从 $2$ 开始,如果该数为素数,就筛掉这个数的所有倍数。即:
$2$ 筛除 $4、6、8、10、12、14、16\cdots$
$3$ 筛除 $6、9、12、15、18、21、24\cdots$
$4$ 是合数,不筛除其他数字
$5$ 筛除 $10、15、20、25、30、35、40\cdots$
$\vdots$

欧拉筛

时间复杂度:$O(n)$

代码实现:

// prime储存素数序列,primesize即素数数量,isprime储存该数是否为素数
int prime[SIZE], primesize = 0;
bool isprime[SIZE];
memset(isprime, 1, sizeof(isprime));
// 特判0、1不是素数
isprime[0] = isprime[1] = false;
// 使用欧拉筛处理>1的情况
for (int i = 2; i < SIZE; i++)
{
    if (isprime[i])
        prime[primesize++] = i;
    for (int j = 0; j <= primesize && i * prime[j] < SIZE; j++)
    {
        isprime[i * prime[j]] = false;
        if (i % prime[j] == 0)
            break;
    }
}

算法结果:

得到一个范围从 0 到 SIZE 的 bool 数组 isprime,每一位储存该数字是否是素数。

得到一个含有 primesize 个数的 int 数组 prime,里面从小到大存放着从 0 到 SIZE 的素数。

算法思路:

埃氏筛会将一个数多次筛除,如 30 会被 2、3、5 筛除三次,浪费一定的时间。
欧拉筛只会用该数的最小质因子筛除该数,例如 30 只会被 2 筛除一次,节约时间。

模拟该算法的操作:从 $2$ 开始

  • $2$ 为素数,将其加入 prime[ ],当前 prime[1] = {2}

    • 筛除 $2*2$
    • $2\%2==0$,停止筛除
  • $3$ 为素数,将其加入 prime[ ],当前 prime[2] = {2, 3}

    • 筛除 $3*2$
    • 筛除 $3*3$
    • $3\%3==0$,停止筛除
  • $4$ 为合数

    • 筛除 $4*2$
    • $4\%2==0$,停止筛除
  • $5$ 为素数,将其加入 prime[ ],当前 prime[3] = {2, 3, 5}

    • 筛除 $5*2$
    • 筛除 $5*3$
    • 筛除 $5*4$
    • 筛除 $5*5$
    • $5\%5==0$,停止筛除
  • $6$ 为合数

    • 筛除 $6*2$
    • $6\%2==0$,停止筛除

​ $\vdots$

该算法的灵魂就是每一步停止筛除的判断,对应到代码即if (i % prime[j] == 0) break;这一条。

为什么这一行代码能让欧拉筛保证数字只被最小质因子筛去?

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 的最小因子。

https://www.cnblogs.com/Miroerwf/p/7776390.html

就拿在 $4\%2==0$ 时停止筛除这个情况举例,当处于这个情况时,如果我们不停下,下一个要筛的就是 $4*3$,但是因为 $4$ 里面包含有 $2$,就说明 $4*3$ 一定能被 $2*6$ 筛去,再往后 $4*4$ 一定能被 $2*8$ 筛去,也就是当满足这个条件后,应当停止筛除。

对比

时间复杂度:

一个为 $O(n\log\log n)$,一个为 $O(n)$,虽说从时间复杂度上看,线性筛绝对占优势,如下图(假设底数为$e$)

但在较小数据范围时,优势较小。而且线性筛内部包含有取模运算,在特定数据范围内可能速度不如埃氏筛。

标签: 埃氏筛, 欧拉筛

添加新评论