Skip to content

L1-028 判断素数

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 400 ms
  • 内存限制: 64 MB

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

输入格式

输入在第一行给出一个正整数N（\le 10），随后N行，每行给出一个小于2^{31}的需要判断的正整数。

输出格式

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

输入样例 

2
11
111

输出样例 

Yes
No

Solution

#include <ctype.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const double PI = 3.14159265358979323846264338327;
const double E = 2.718281828459;
const double eps = 1e-6;
const int MAXN = 0x3f3f3f3f;
const int MINN = 0xc0c0c0c0;
const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;
int isPrime(int x) {
    int flag;
    int n, m;
    if (x <= 1)
        flag = 0;
    else if (x == 2 || x == 3)
        flag = 1;
    else if (x % 2 == 0)
        flag = 0;
    else {
        m = sqrt(x) + 1;
        for (n = 3; n <= m; n += 2) {
            if (x % n == 0) {
                flag = 0;
                break;
            } else {
                flag = 1;
            }
        }
    }
    return flag;
}

int main() {
    int n;
    cin >> n;
    int num;
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        if (isPrime(num))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}
Last update: May 4, 2022
Back to top