L1-028 判断素数 （10 分）

https://pintia.cn/problem-sets/994805046380707840/problems/994805106325700608

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

输入格式：

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

输出格式：

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

输入样例：

2

11

111

输出样例：

Yes

No

在遇到i*i<=x的时候一定要想到改成 i <= sqrt(x)!!!! 因为没这样干贡献了若干次超时

还有要考虑输入的数字 <= 1的情形  很有PTA特色

做了很好的优化 不过速度还比一个个算更慢 因为数据太小了吧

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

int arr[10];

vector <int> pr;

void findpr(int x) {

for (int i = 4; i <= sqrt(x); i++) {

int fl = 1;

for (int j = 0; j < pr.size() && pr[j] <= sqrt(i); j++) {

if (i % pr[j] == 0)  {

fl = 0;

break;

}

}

if (fl) pr.push_back(i);

}

}

int main() {

int N, M = 0;

pr.push_back(2);

pr.push_back(3);

scanf("%d", &N);

for (int i = 0; i < N; i++) {

scanf("%d", &arr[i]);

M = max(M, arr[i]);

}

findpr(M);

for (int i = 0; i < N; i++) {

int fl = 1;

for (int j = 0; j < pr.size() && pr[j] <= sqrt(arr[i]); j++) {

if (arr[i] % pr[j] == 0) {

fl = 0;

break;

}

}

if (fl && arr[i] > 1) printf("Yes\n");

else printf("No\n");

}

return 0;

}