筛法求素数

发表于 更新于 分类于 ， 阅读次数： 本文字数： 240 阅读时长 ≈ 1 分钟

本文将介绍 埃拉托斯特尼筛法 和 欧拉线性筛法 的基本原理，并以此思路实现这两种求素数的算法。

筛法求素数

埃拉托斯特尼筛法

基本思路

当一个数是素数的时候，它的倍数肯定不是素数，对于这些数可以直接标记筛除。

时间复杂度

\(O(nloglogn)\)

算法实现

java

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
public class SimpleSieve {
    public static int[] sieve(int n){
        int[] mark = new int[n+1]; //元素值为0代表是素数
        int counter = 0;
        for (int i = 2; i <= n; i++){
            if (mark[i] == 0){
                counter++;
                for (int j = 2 * i; j <= n; j += i){
                    mark[j] = 1;
                }
            }
        }
        int[] primes = new int[counter];
        counter = 0;
        for (int i = 2; i <= n; i++){
            if (mark[i] == 0) primes[counter++] = i;
        }
        return primes;
    }

    public static void main(String[] args){
        int[] ans = SimpleSieve.sieve(100);
        for (int e: ans) {
            System.out.println(e + " ");
        }
    }
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from typing import List


def eratosthenes_sieve(n: int) -> List[int]:
    ans = []
    marks = [True] * n
    for i in range(2, n):
        if marks[i]:
            ans.append(i)
            for j in range(i + i, n, i):
                marks[j] = False
    return ans


if __name__ == "__main__":
    print(eratosthenes_sieve(100))

欧拉线性筛法

基本思路

任意一个合数（2 不是合数），都可以表示成素数的乘积。

每个合数必有一个最小素因子，如果每个合数都用最小素因子筛去，那个这个合数就不会被重复标记筛去，所以算法为线性时间复杂度。

例如合数 30 = 2 * 3 * 5 ，这个合数一定是被最小素因子 2 筛去的。

时间复杂度

\(O(n)\)

算法实现

java

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
import java.util.ArrayList;

public class EulerSieve {
    public static int[] sieve(int n){
        int[] mark = new int[n+1]; //元素值为0表示该元素下标值为素数
        ArrayList<Integer> primes = new ArrayList<>();
        for (int i=2; i<=n; i++){
            if (mark[i] == 0) primes.add(i);
            for (int j=0; j<primes.size() && i*primes.get(j)<=n; j++){
                mark[i*primes.get(j)] = 1;
                if (i % primes.get(j) == 0)
                    break;
            }
        }
        int[] ans = new int[primes.size()];
        for (int i=0; i<primes.size(); i++)
            ans[i] = primes.get(i);
        return ans;
    }

    public static void main(String[] args){
        int[] ans = EulerSieve.sieve(100);
        for (int e: ans) {
            System.out.println(e + " ");
        }
    }
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from typing import List


def euler_sieve(n: int) -> List[int]:
    ans = []
    # True 表示该下标值为素数
    marks = [True] * n
    for i in range(2, n):
        if marks[i]:
            ans.append(i)

        j = 0
        while j < len(ans) and i * ans[j] < n:
            marks[i * ans[j]] = False
            if i % ans[j] == 0:
                break
            j += 1
    return ans


if __name__ == "__main__":
    print(euler_sieve(100))

References

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

https://www.jianshu.com/p/f16d318efe9b