[C++知识库]AcWing 868. 筛质数

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=1000005;
int primes[N],cnt;
bool st[N];
void get_primes(int n){//埃氏筛统计素数
	for(int i=2;i<=n;i++){
		if(!st[i]){
			primes[cnt++]=i;
			for(int j=i*2;j<=n;j+=i) st[j]=true;
		}		
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	get_primes(n);
	printf("%d\n",cnt);
	//for(int i=0;i<cnt;i++) cout<<primes[i]<<" ";
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=1000005;
int primes[N],cnt;
bool st[N];
void get_primes(int n){//线性筛  
	for(int i=2;i<=n;i++){
		if(!st[i]) primes[cnt++]=i;
		for(int j=0;primes[j]<=n/i;j++){
			st[primes[j]*i]=true;
			if(i%primes[j]==0)break;//primes[j]一定是i的最小质因子
		} 		
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	get_primes(n);
	printf("%d\n",cnt);
	//for(int i=0;i<cnt;i++) cout<<primes[i]<<" ";
    return 0;
}
/*
n只会被最小质因子筛掉
1. i%primes[j]==0 
   primes[j]一定是i的最小质因子  primes[j]一定是primes[j]*i的最小质因子
2. i%primes[j]!=0
   primes[j]一定小于i的所有质因子  primes[j]一定是primes[j]*i的最小质因子
对于一个合数x，假设primes[j]是x的最小质因子，当i枚举到x/primes[j]的时候这个合数会被筛掉
*/