洛谷题解P5736 【深基7.例2】质数筛

原题传送门

0.前言 简单的素数筛例题
1.思路

显然这是一道很简单的素数筛问题，我用埃氏筛来解决（我才不说我不会写欧拉筛）
不会埃氏筛的同学可以戳这里——>link

2.代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline void read(int &x){
	int f=1;
	char ch=getchar();
	x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
int n,mx;
int a[101];
bool isprime[100001];
int main(){
	read(n);
	memset(isprime,true,sizeof(isprime));
	for(int i=1;i<=n;i++) {
		read(a[i]);
		mx=max(mx,a[i]);	//记录最大值，因为n的值没有最大值大 
	}
	isprime[0]=isprime[1]=false;
	for(int i=2;i<=mx;i++){	//埃氏筛 
		if(isprime[i]){
			for(int j=2*i;j<=mx;j+=i){
				isprime[j]=false;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(isprime[a[i]]){
			printf("%d ",a[i]);
		}
	}
	return 0;
}