一个大于$1$的自然数，如果除了$1$和它自身外，不能被其他自然数整除则称该数为质数。

例如$7$就是一个质数，因为它只能被$1$和$7$整除。

现在，给定你$N$个大于$1$的自然数，请你依次判断这些数是否是质数。

输入格式

第一行包含整数$N$，表示共有$N$个测试数据。

接下来$N$行，每行包含一个自然数$X$。

输出格式

每个测试用例输出一个结果，每个结果占一行。

如果测试数据是质数，则输出 X is prime，其中$X$是测试数据。

如果测试数据不是质数，则输出 X is not prime，其中$X$是测试数据。

数据范围

$1≤N≤100$
$1<X≤107$

样例

20
839
312
397
804
145
276
127
489
521
331
577
57
534
88
379
98
59
5
487
189

代码（非暴力）

先巧妙的将范围内所有的质数筛出来，最后统一判断。不用每次找他是不是质数而重头找一次。理论上复杂度是小于$nlog(n)$的，只与$X$的取值范围有关。

但我的代码为什么找出的数组内数字不是0或1？而是其他2或者3或者更大的数字。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7+9;
int notprime[N];// 非质数集合，即和数的集合（该数为和数，就被标记为1）


int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    for(int i=2;i<=sqrt(N);i++)// 将可能的质数遍历
    {
        // 该数已经被标记为非质数，其倍数也会被标记，不再便利
        if(notprime[i]) continue;
        // 该数未被标记，其倍数为和数，从该数的两倍开始标记
        for(int j=2;i*j<N;j++){
            notprime[i*j] ++;
        }
    }
    int n,a;cin >> n;
    while(n--){
        cin >> a;
        if(notprime[a])cout << a << " is not prime\n";
        else cout << a << " is prime\n";
    }

    return 0;
}

正解 AC

上面的代码时将所有素数求出来了，但其实他只要能被除了1和本身的数整除，那就可以直接跳出了

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while (n -- ){
        int x;
        bool is_prime=true;
        cin>>x;
        if(x==1) cout<<x<<" is not prime"<<endl;
        else{
            int i;
            for(i=2;i<=x/i;i++)
            {
                if(x%i==0) 
                {
                    is_prime=false;
                    break;
                }
                else is_prime=true;
            }
            if(is_prime) cout<<x<<" is prime"<<endl;
            else cout<<x<<" is not prime"<<endl;
        }
    }
    return 0;
}