4393: 【入门】筛素数(2136)

埃筛

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
bool f[N]; //标记素数，false表示是素数,true表示不是 
int primes[N],k=0; //存储所有的素数 
int n;
int main(){
    cin>>n;
    //特判特殊的数 
    f[0]=true;
    f[1]=true;
    //循环所有的数，逐个判断 
    for(int i=2;i<=n;i++) {
    	//如果i是素数，i的倍数不是素数 
    	if(!f[i]){
    		k++;
    		primes[k]=i;
    		//将i的倍数标记为不是素数 
    		for(int j=i+i;j<=n;j=j+i){
    			f[j]=true; //标记不是素数 
			}
		}
	}
	cout<<k; 
	return 0;
}

埃筛（不用数组存起来）

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
bool f[N]; //标记素数，false表示是素数,true表示不是 
int primes[N],k=0; //存储所有的素数 
int n;
int main(){
    cin>>n;
    //特判特殊的数 
    f[0]=true;
    f[1]=true;
    k=n-1;
    //循环所有的数，逐个判断 
    for(int i=2;i*i<=n;i++) {
    	//如果i是素数，i的倍数不是素数 
    	if(!f[i]){
    		//k++;
    		//primes[k]=i;
    		//将i的倍数标记为不是素数 
    		for(int j=i+i;j<=n;j=j+i){
    		    if(!f[j]) {
    		        f[j]=true; //标记不是素数 
    		        k--;
    		    }
    			
			}
		}
	}
	cout<<k; 
	return 0;
}

线性筛

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
bool f[N]; //标记素数，false表示是素数,true表示不是 
int primes[N],k=0; //存储所有的素数 
int n;
/*
线性筛：每个合数只被自己的最小质因数筛除
比如：6在埃筛能被2筛除，又能被3筛除
我们希望在线性筛中，6仅仅被最小质因子，也就是2筛除 
*/ 
int main(){
    cin>>n;
    //特判特殊的数 
    f[0]=true;
    f[1]=true;
    //循环所有的数，逐个判断 
    for(int i=2;i<=n;i++) {
    	//如果i是素数，i的倍数不是素数 
    	if(!f[i]){
    		k++;
    		primes[k]=i;
        }
    	//每个合数，只能被自己的最小质因子筛除
		//j循环的是primes数组  
    	for(int j=1;i*primes[j]<=n;j++){
    		f[i*primes[j]]=true; //将该数筛掉
			//如果i%primes[j]==0
			//i*primes[j+1]%primes[j]==0
			if(i%primes[j]==0) break; 
		}
	}
	cout<<k; 
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
bool is_prime[MAXN];
int prime[MAXN];
//埃筛 
int Er_Sieve(int n){
	int tot=0;
    memset(is_prime,1,sizeof(is_prime));
    is_prime[1] = is_prime[0] = 0;
    for(int i = 2;i <= n;i++){
        if(!is_prime[i]) continue;
        prime[++tot] = i; //prime[]存储了[1,n]的所有质数
        for(int j = i*2; j <= n; j+=i) 
	        is_prime[j]=0; //j为合数
    }
    return tot;
}
//线性筛（欧拉筛） 
int Eu_Sieve(int n){
	int tot=0;
    memset(is_prime,1,sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    for(int i = 2; i <= n; i++){
        if(is_prime[i])
            prime[++tot] = i; //prime[]存储了[1,n]的所有质数
        for(int j = 1; j <= tot && prime[j]*i <= n; j++){ //关键一
            is_prime[prime[j]*i] = 0;
            if(i%prime[j] == 0) break;// 关键二
        } 
    }
    return tot;
}
int main(){
    int n;
    cin>>n;
    cout<<Er_Sieve(n);
	return 0;
}