如何判断一个素数（反正没人看，随便写写）_输入n个不大于100000的正整数,要求全部储存在数组中,去除掉不是质数的数字,依

什么是素数（该不会有人连这都不知道吧）：素数就是只能被自己和1整除的数(1不是质数哦）。

所以就只需要保证n除以2到n-1没有余数就行了

bool isprime(int n)
{
cin>>n;//n是整数
if(n<2)//0和1都不是质数所以要用这个条件来排除
{
return false;
}
for(int i=2;i<=n-1;i++)
{
if(n%i==0)
return false;
}
return ture;
}
 

举一个例子:

题目描述

输入n个不大于100000的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。

输入格式

第一行输入一个正整数 n，表示整数个数。

第二行输入 n 个正整数 ai​，以空格隔开。

输出格式

输出一行，依次输出 ai​ 中剩余的质数，以空格隔开。

输入输出样例

输入

5
3 4 5 6 7

输出 

3 5 7

说明/提示

数据保证，1≤n≤100，1≤ai​≤100000。

#include<iostream>
using namespace std;
bool isprime(int n)
{
    if(n<2)
    {
        return false;
    }
    for(int i=2;i<n-1;i++)
    {
    if(n%i==0)
    return false;
    }
    return true;
}
int n=0,a[100000]={0};
int main()
{
  cin>>n;  
   for(int i=0;i<n;i++) 
    {
        cin>>a[i];
    }
    
    for(int i=0;i<n;i++)
    {
        if(isprime(a[i])==true)
        cout<<a[i]<<' ';
    }
    
    return 0;
}

运行结果如下：

当然了还是可以优化以下的

想一下如果一个数的不是质数的话，那么他的平方根的左边和右边一定各有一个因数（这就是数学知识了），比如6的两个因数是2和3，这两个因数就在根号下6的左右两边。

优化后的代码如下：

bool isprime(int n)
{
double k=sqrt(n);
for(int i=0;i<=k;i++)
{
if(n%i==0)
return false;
}
return true;
}

如果按照上面的例子，完整代码如下

#include<iostream>
#include<cmath>
using namespace std;
int n=0,a[100000]={0};
bool isprime(int n)
{
if(n<2)
return false;
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)
return false;
}
return true;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
if(isprime(a[i])==true)
cout<<a[i]<<' ';
}
return 0;
}

运行结果如下