pta:L1-028 判断素数

L1-028 判断素数

本题的目标很简单，就是判断一个给定的正整数是否素数。

输入格式：

输入在第一行给出一个正整数$N$(≤ 10)，随后$N$行，每行给出一个小于$2^{31}$的需要判断的正整数。

输出格式：

对每个需要判断的正整数，如果它是素数，则在一行中输出Yes，否则输出No。

输入样例：

2
11
111

输出样例：

   Yes
   No

思路

难点就是求解素数。
定义：素数：质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数;否则称为合数。
所以1不为素数。
思路一：暴力解 O(n)

 for (i = 2; i <=n/ 2; i++) {
        if (n % i == 0)
            return 0;
    }

思路二：$O(\sqrt{(}n))$

 for (i = 2; i <= (int)sqrt(n); i++) {
        if (n % i == 0)
            return 0;
    }

解答

#include<bits/stdc++.h>
using namespace std;
bool Judege_Su(int n)
{
    if(n==1) return 0;//不可少 1这种情况
    for(i=2;i<=sqrt(n);++i)
    {
        if(0==n%i) return 0;
    }
    return 1;
}
int main()
{
    int N;
    cin>>N;
    int temp;
    vector<int> ans;
    bool flag;
    for(int i=0;i<N;++i)
    {
        cin>>temp;
        ans.push_back(temp);
    }
    for(int &it:ans)
    {
        flag=Judege_Su(it);
        if(flag==0)
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    }
    return 0;
    
}