I've always wanted to summarize the prime sieve method, Can't always open air, 下面用C++和Python實現, 簡單講一下思路, 主要參考了oi-wiki1, A dozen leaders of the competition to create knowledge collection.
思路很簡單, 就是通過遍歷, To find out is the number of primes of all multiples, 將其標記為合數, So a trip to traverse all down, Can get all the prime Numbers.
from time import time
from numba import jit
n = int(1e6)
@jit(nopython=True)
def Eratosthenes(n):
p = 0 # the number of prime
prime = [] # save prime
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):# 從第一個素數2開始
if is_prime[i]:# 如果是素數
prime.append(i)#加入素數列表
p = p + 1# 素數個數+1
if i * i <= n:# Don't make an array, These two lines of code can not write, 直接進入while判斷
j = i * i
while j <= n:
is_prime[j] = False
j = j + i#Here is the mark of a multiple of, 通過j+=iWay to add multiple
print(prime, "\nthe number of prime is: ", p)
s = time()
Eratosthenes(n)
e = time()
print(f"Eratosthenes: time is {
e-s}s")
'''the number of prime is: 78498 Eratosthenes: time is 0.23691391944885254s'''
from time import time
# from numba import jit
n = int(1e6)
# @jit(nopython=True)
def Eratosthenes(n):
ans = []#存放素數
cnt = 0
is_prime = [True] * (n + 1)#標記合數
is_prime[0] = is_prime[1] = False# 初始條件
for i in range(2, int(n**.5) + 1):#優化的部分
""" Because the only judgment here beforesqrt(n)個數(This is to mark all sum Numbers), Can only be obtained by the second traversal of thebool數組`is_prime`To find out all the prime Numbers, Not like the former method has completed by once prime Numbers stored/計數 """
if is_prime[i]:
j = i * i
while j <= n:
is_prime[j] = False
j += i
for j in range(n + 1):
if is_prime[j]:
ans.append(j)
cnt += 1
print(ans, "\nthe number of prime is: ", cnt)
s = time()
Eratosthenes(n)
e = time()
print(f"Eratosthenes: time is {
e-s}s")
'''the number of prime is: 78498 Eratosthenes: time is 0.23756694793701172s with jit: the number of prime is: 78498 Eratosthenes: time is 0.3765590190887451s '''
Optimization is mainly manifested in hereThrough the number中了, But as a result of a problem is not through a traverse to find all prime Numbers, Need extra traversal.
時間復雜度O(N), To optimize the equivalent to the code above, Main ideas or sieve method, 但是設置了終止條件, Can't make repeated traversal, 提高了運行效率, 這在C++中有所體現.
但是在使用Python進行測試的時候, Erichsen screen turned out to be the fastest, No matter with uselessnumba優化, Are as slow, 感覺可能是PythonAn array a certain optimization, Use the back giveC++Code there would be no problem.
from time import time
# from numba import jit
# @jit(nopython=True)
def euler():
MAXN = int(1e6)
pri = []#存儲素數
vis = [True] * (MAXN + 1)#標記合數:False
cnt = 0#計數
for i in range(2, MAXN):
if vis[i]:#如果是素數, Storage and count
pri.append(i)
cnt += 1
for j in range(cnt):#This cycle need to pay attention to
if i * pri[j] > MAXN:# 判斷數組越界
break
vis[i * pri[j]] = False # 倍數標記為合數
if i % pri[j] == 0: # 防止重復標記
# 這步是EulerThe core of the sieve method
""" 可以舉這樣一個例子: 12=3x4=2x6,In the list of prime Numbers as[2,3],i=4Has marked 所以在i=6時候,i%pri[j]=6%2==0,This time will not repeat tag12了, So are the other like12So how prime factor sum Numbers will not be repeated tags,This completes the optimization of erichsen screen """
break
print(pri, "\nthe number of prime is: ", cnt)
s = time()
euler()
e = time()
print(f"euler: time is {
e-s}s")
'''the number of prime is: 78498 euler: time is 0.5525140762329102s with numba jit: the number of prime is: 78498 euler: time is 0.40300703048706055s '''
The integration of theC++版本的代碼, 如下:
#include <iostream>
using namespace std;
constexpr int maxn = 1e8+10;
bitset<maxn> pri;
int primes[maxn];
void era() {
int N = 1e8,cnt=0;
double s=clock();
for (int i=2;i*i<=N;++i){
if (!pri[i]){
for (int j=i*i;j<=N;j+=i) pri[j]=1;
}
}
for(int i=2;i<=N;i++)
if(!pri[i])cnt++;
double e=clock();
printf("%d\ntime = %.0lftic",cnt,e-s);
/*5761455 time = 4252883tic[Finished in 4.9s]*/
}
void euler() {
int N = 1e8,cnt=0;
double s=clock();
for (int i=2;i<=N;++i){
if (!pri[i])primes[++cnt]=i;
for (int j=1;i*primes[j]<=N;j++) {
pri[i*primes[j]]=1;
if (i%primes[j]==0)break;
}
}
double e=clock();
printf("%d\ntime = %.0lftic",cnt,e-s);
/*5761455 time = 2730051tic[Finished in 3.5s]*/
}
int main(int argc, char const *argv[])
{
// era();
euler();
return 0;
}
P.S. Instead, it isC++The code is more concise and compact.
篩法 - OI Wiki (oi-wiki.org); ︎
