埃氏筛与线性筛（欧拉筛）

埃氏筛/埃拉托斯特尼筛法

C++

const int N=1e5+10;
int pri[N],cnt=0;
bool is_pri[N];
int prime(int n){memset(is_pri,1,sizeof(is_pri));is_pri[0]=is_pri[1]=0;for(int i=2;i<=n;i++){if(is_pri[i]){pri[cnt++]=i;for(int j=2*i;j<=n;j+=i)is_pri[j]=0;}}return cnt;//返回素数的个数
}

python

n=100
is_pri=[1]*(n+1)
pri=[]
def prime(n):is_pri[0]=is_pri[1]=0for i in range(2,n+1):if is_pri[i]==1 pri.append(i)for j in range(2*i,n+1,i):is_pri[j]=0
# testing-program
prime(n)
for i in range(len(pri)):print(pri[i],end=' ')

 线性筛（欧拉筛）

简单讲下原理：注意看循环中每次筛掉的合数i*pri[j]，然而当i\%pri[j]==0时，则对于后面的pri[j+k]*i=pri[j+k]*pri[j]*r=pri[j]*(r*pri[j+k])，可以被更小的质数筛掉（每个合数都表示成最小质因数*某个数，保证被最小质因数筛掉）

ps：之前本人一直在考虑break后会不会后面的数会被误判为合数（只是我想多了）

对于每个x，x=pri*t，在i=t时，is\_pri[x]就会被赋值为0(在i遍历到x之前)

C++ 

const int N=1e5+10;
int pri[N],cnt=0;
bool is_pri[N];
void prime(int n){memset(is_pri,1,sizeof(is_pri));is_pri[0]=is_pri[1]=0;for(int i=2;i<=n;i++){if(is_pri[i]) pri[cnt++]=i;for(int j=0;j

n=100
is_pri=[1]*(n+1)
pri=[]
def prime(n):is_pri[0] = is_pri[1] = 0for i in range(2,n+1):if is_pri[i]==1 :pri.append(i)for j in range(len(pri)):if i*pri[j]>n | j>=len(pri) :breakis_pri[i*pri[j]] = 0if i%pri[j] == 0 :break
# testing-program
prime(n)
for i in range(len(pri)):print(pri[i],end=' ')

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！