【数论】欧拉筛法-埃拉托斯特尼筛法

欧拉筛法

概念

筛法就是求出小于等于n的所有素数的方法，找到一个素数后，就将它的倍数标记为合数，也就是把它的倍数“筛掉”。如果一个数没有被比它小的素数“筛掉”，那它就是素数。

思路

bool isprime[MAXN]; // isprime[i]标记`i`是否是素数的数组
int prime[MAXN]; // 目前的素数列表
int n; // 筛选上限
int cnt = 0; // 已经筛出的素数数量

void euler()
{
    memset(isprime, true, sizeof(isprime)); //先全部标记为素数
    isprime[1] = false; //已知，1不是素数
    for(int i = 2; i <= n; i++) // i从2循环到n（外层循环）
    {
        if(isprime[i])//isprime[i] == 1
            prime[++cnt] = i;
        // 如果i没有被前面的数筛掉，则i是素数，此处prime[0]元素并未被使用，保持数值与序号对应
        for(int j = 1; j <= cnt && i * prime[j] <= n; j++)
        // 使用j循环枚举现在已经筛出的素数,以筛掉i的素数倍，即i的prime[j]倍
        {
            isprime[i * prime[j]] = false;
            // 倍数标记为合数，也就是i用prime[j]把i * prime[j]筛掉了
            if(i % prime[j] == 0) 
                break;
            // 如果i整除prime[j]，退出循环，这样可以保证线性的时间复杂度
        }
    }
}

假设要筛出n以内的素数。我们先把所有数标记为素数。枚举i从2到n，所以因为i是从小到大的，如果i没有被比它小的数标记为合数，那i就是素数（任意合数的因数一定比它本身小，若i没有被前面的数筛掉，那么它就没有比自己小的因数，当然它就是素数），加入素数列表。

现在用i来筛后面的数，枚举已经筛出来的素数prime[j]（j∈[1,cnt]），标记i * prime[j]为合数（i ≥ 2，prime[j] ≥ 2，它们的乘积一定为合数），当i是prime[j]的倍数时退出循环，i++。

正确性证明

假设我们要筛掉合数a，且a的最小质因数为P1，令a = P1 * b ,那么显然b < a，b先被外层循环碰到。现在b要筛掉它的倍数。

因为P1是a的最小质因数，所以b的最小质因数必不小于P1，这样就保证b筛掉a前不会在if(i % prime[j] == 0) break;处跳出循环。

即使b的最小质因数等于P1，也会先筛掉a后再退出循环。这样就保证了每个合数都会被筛掉。

时间复杂度证明

欧拉筛法的时间、空间复杂度为Θ(n)。

空间复杂度是显然的，下面证明时间复杂度为线性。

我们的核心就是要证明一个合数只会被筛掉一次，即标记isprime[n]=1一次。首先，对于a = P1 * b，b当然只会筛掉a一次，因为我们从小到大枚举prime[j]，也就是说b * prime[j]递增，因此不可能遇到a两次。会不会有其他的数筛掉a呢？假设a又被c筛掉了，其中a = Px * c，Px就是c用来筛掉a的prime[j]。

• 若c > b，则Px < P1，与P1是a最小的质因数矛盾，假设不成立；
• 若c < b，则Px > P1，这意味着P1是c的质因数。那么c从小到大筛掉它的素数倍，在筛到P1 * c时就break了，所以根本轮不到a。

综上所述，每个数都只会被筛掉一次，再加上外层的i的循环是线性复杂度，总的时间复杂度是线性的。

示例

来自：头歌-Python大数据与人工智能实践

计算并输出指定范围内的所有素数。

第一行输入正整数n，表示测试样例组数，接下来输入n行，每行输入两个正整数a和b，要求输出a和b之间（包括a和b）所有的素数，保证a<b，且b不超过10^7

测试输入：

2
30,100
999670,1000000
123

预期输出：

[31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
[999671, 999683, 999721, 999727, 999749, 999763, 999769, 999773, 999809, 999853, 999863, 999883, 999907, 999917, 999931, 999953, 999959, 999961, 999979, 999983]
12

CODE:

from math import sqrt

class Solution():
    def solve(self, l, r):
        '''
        :type l, r: int
        :rtype : list
        求得[l, r]范围内的所有素数，并将其返回
        '''
        
        def is_prime(x):
            '''
            通过素数表判断整数是不是素数
            '''
            if x == 1:
                return False
            for n in prime_table:
                if x < n * n:
                    return True
                #如果满足上述条件，说明n之前的素数里没有x的因数
                if x % n  == 0:
                    return False

        def ouler(x):
            vis = [0 for i in range(x+1)]
            prime_table = []
            ln = 0
            for n in range(2, x+1):
                if vis[n] == 0:
                    prime_table.append(n)
                    ln += 1
                for j in range(ln):
                    if n * prime_table[j] > x:
                        break
                    vis[n * prime_table[j]] = 1
                    if n % prime_table[j] == 0:
                        break
            return prime_table
        
        
        prime_table = ouler(10000)
        ans = []
        for n in range(l, r+1):
            if is_prime(n):
                ans.append(n)
        return ans

埃拉托斯特尼筛法

埃拉托斯特尼筛法 sieve of Eratosthenes，简称埃氏筛，也称素数筛。

从2开始，将每个素数的各个倍数，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列。

定出要筛数值的范围n，找出$\sqrt{n}$以内的素数$\displaystyle p_{1}，p_{2},\dots,p_{k}$。先用2去筛，把2留下，把2的倍数剔除掉；再用下个素数3筛，把3留下，把3的倍数剔除掉；接下去用下个素数5筛，把5留下，把5的倍数剔除掉，如果最大数不大于最后一个标出的素数的平方，那么剩下的所有的数都是质数，否则继续上述过程。

def eratosthenes(n):
    # 初始所有的都为True
    IsPrime = [True] * (n + 1)
    # 100**0.5 = 10
    for i in range(2, int(n ** 0.5) + 1):
        # i在2-10范围内如果是素数
        if IsPrime[i]:
            # 从i平方开始往后去掉，即置标志位为false
            for j in range(i * i, n + 1, i):
                IsPrime[j] = False
    # 输出所有标志位为True的就是素数
    return [x for x in range(2, n + 1) if IsPrime[x]]


print(eratosthenes(100))

Reference

1. 埃拉托斯特尼筛法 ↩
2. 埃拉托斯特尼筛法详解及实现 ↩
3. 欧拉筛法 ↩
4. 厄拉托塞师（Eratosthenes）筛法 ↩