筛法求素数

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

埃拉托斯特尼筛法

基本思路

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

时间复杂度

\(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