20240322每日一题题解
Problem
输入 \(n\) 个不大于 \(10^5\) 的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。
第一行输入一个正整数 \(n\)，表示整数个数。
第二行输入 \(n\) 个正整数 \(a_i\)，以空格隔开。
输出一行，依次输出 \(a_i\) 中剩余的质数，以空格隔开。
例如，输入
5
3 4 5 6 7
应当输出
3 5 7
注意数据范围：\(1\le n\le100\)，\(1 \leq a_i \leq 10^5\)。
Solution
判断素数最最暴力的办法，就是枚举\([2,x-1]\)区间内有没有数字\(i\)使得\(x\equiv 0 \pmod i\)。
我们将这一循环判断写成函数，然后对于输入的每个数，调用函数判断其是否为质数。如果是质数，则输出这个数字；如果不是，则跳过。这样就不用把所有数据读取存入数组中了。
#include<iostream>
using namespace std;
bool judge_prime(int x)
{
if(x==1) return 0;
for(int i=2;i<x;i++)
{
if(x%i==0) return 0;
}
return 1;
}
int main()
{
int n;cin>>n;
for(int i=1,a;i<=n;i++)
{
cin>>a;
if(judge_prime(a)) cout<<a<<" ";
}
return 0;
}
优化
其实我们不需要枚举\(i\in[2,x-1]\)，只需要枚举\([2,\sqrt{x}]\)即可。因为x的因数一定是成对出现的（除了\(\sqrt x\)），并且如果一个因数\(p_i\le\sqrt x\)，则定有其对应的因数\(\frac{x}{p_i}\ge \sqrt x\)。
所以我们可以修改循环条件为i*i<=x
bool judge_prime(int x)
{
if(x==1) return 0;
for(int i=2;i*i<=x;i++)
{
if(x%i==0) return 0;
}
return 1;
}
再优化
可以将\(10^5\)以内的质数都预处理出来，使用到了埃氏筛
#include<iostream>
using namespace std;
bool prime[100010];//1表示不是质数，0表示是质数
int main()
{
prime[1]=1;//1不是质数
for(int i=2;i<=100000;i++)
{
if(prime[i]==0)//如果i是质数
{
for(int j=i*2;j<=100000;j+=i)//那么将i的倍数都打上标记
{
prime[j]=1;
}
}
}
int n;cin>>n;
for(int i=1,a;i<=n;i++)
{
cin>>a;
if(prime[a]==0) cout<<a<<" ";
}
return 0;
}
当然，在这道题里面，这种做法优势不大。
对于数字更大更多（例如\(n\le10^6,a_i\le10^8\)的范围），有兴趣可以了解一下线性筛，例题点我。
对于快速判断大质数，有兴趣可以去了解Miller–Rabin 素性测试。