GESP5级语法知识（十）：初级数论（三）

埃氏筛法：

#include <iostream>
using namespace std;
const int N=1e6+1;
int pri[N];
void prime(int n){for(int i=2;i*i<=n;i++){if(pri[i]==0){ // 如果i为素数for(int j=i+i;j<=n;j+=i){pri[j]=1; // 将i的倍数标记为合数}}}
}
int main(){int n;cin>>n;prime(n);for(int i=2;i<=n;i++){if(pri[i]==0)cout<<i<<" ";}	return 0;
}

线性筛法：

#include <iostream>
using namespace std;
const int N=1e6+1;
int pri[N];
int primes[N],p;
void prime(int n){for(int i=2;i<=n;i++){if(!pri[i])primes[p++]=i;for(int j=0;j<p&&primes[j]*i<=n;j++){pri[primes[j]*i]=1;if(i%primes[j]==0)break;}}
}
int main(){int n;cin>>n;prime(n);for(int i=0;i<p;i++)cout<<primes[i]<<" ";return 0;
}