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

题目

输入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;
}