题目
输入n个不大于105的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。
输入输出格式
输入格式
第一行输入一个正整数n，表示整数个数。
第二行输入n个正整数，以空格隔开。
输出格式
输出一行，依次输出中剩余的质数，以空格隔开。
输入输出样例
输入样例
5
3 4 5 6 7输出样例
3 5 7代码
（1）开根
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
bool isprime(int x){//判断是否素数
if(x<=1) return false;//如果小于2，一定不是素数
for(int i=2;i<=sqrt(x);i++){
if(x%i==0) return false;//如果可以整除，那么不是素数
}
return true;//是素数
}
int main(){
int n,a;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
if(isprime(a)){
cout<<a<<" ";//是素数，就输出
}
}
return 0;
} （2）欧式筛法（素数乘合数为合数）
#include <bits/stdc++.h>
using namespace std;
long long n,m;
bool vis[10000001]={1,1};//0，1均既不是素数，也不是合数，所以先标记为不是
int Prime[10000001],k;
void prime(long long n)
{
for(int i=2;i<=n;i++)//最小的素数是2
{
if(!vis[i])
{
Prime[++k]=i;//如果是素数就标记一下
}
for(int j=1;j<=k;j++)//j小于当前所有的素数的个数
{
if(Prime[j]*i>n)
{
break;
}
vis[Prime[j]*i]=true;//用素数依次×i，结果标记为合数
if(i%Prime[j]==0)
{
break;
}
}
}//欧拉筛法，就是拿当前的数×之前的筛出来的素数，这个数即为合数
}
int main()
{
cin>>n;
prime(100001);//在10的5次方范围内筛素数
for(int i=1;i<=n;i++)
{
int t;
cin>>t;
if(!vis[t])//上面标记过了，这时输入后直接判断就行了
{
cout<<t<<" ";
}
}
return 0;
} （3）埃氏筛法（素数的整数倍均为合数）
#include <bits/stdc++.h>
using namespace std;
bool vis[100001]={1,1};//0,1标为不是
int n;
void Era(int qwq)
{
for(int i=2;i<=qwq;i++)
{
if(vis[i])
{
continue;
}//是合数就不执行
for(int j=i*2;j<=qwq;j+=i)//从i×2开始筛，因为经过判断后i为素数
{
vis[j]=true;//j=i的倍数，每次加i，即为i的倍数每次加1，p数组的第j个元素标为合数
}
}
}
int main()
{
cin>>n;
int tmp;
Era(100001);
for(int i=1;i<=n;i++)
{
scanf("%d",&tmp);
if(!vis[tmp])//已经记下了，判断一下即可
{
cout<<tmp<<" ";
}//真就不是，假就是
}
return 0;
}
