0%

素数的筛法:埃氏筛与欧拉筛

记录筛法(埃拉托斯特尼/欧拉)的伪代码实现。

Sieve of Eratosthenes 埃氏筛

S_ERAT(N)
let S[0..N] be a new array
for i <- 0 to N
S[i] <- False
let P[0..N] be a new array
counter <- 0
for i <- 2 to N
if S[i] = False
P[counter] <- i
counter <- counter + 1
for j <- i + i; j <= N; j <- j + i
S[j] <- True
return P

Sieve of Euler 欧拉筛

S_EULER(N)
let S[0..N] be a new array
for i <- 0 to N
S[i] <- False
let P[0..N] be a new array
counter <- 0
for i <- 2 to N
if S[i] = False
P[counter] <- i
counter <- counter + 1
for j <- 0; i * P[j] <= N; j <- j + 1
S[i * P[j]] <- True
if i mod P[j] = 0
break
return P