AcWing 726. 质数 ---- C++ 筛选法
原题链接
中等
作者:
cheng2099
,
2021-01-16 21:01:39
,
所有人可见
,
阅读 1308
#include <iostream>
using namespace std;
const int maxn = 1e7 + 10;
bool p[maxn] = {0};
void Find_Prime() {
for (int i = 2; i < maxn; i++) {
if(p[i] == false) {
for (int j = i + i; j < maxn; j += i) {
p[j] = true;
}
}
}
}
int main() {
Find_Prime();
int n;
scanf("%d", &n);
int data;
while (n--) {
scanf("%d", &data);
if (p[data]) {
printf("%d is not prime\n", data);
} else {
printf("%d is prime\n", data);
}
}
return 0;
}
在超时的边缘试探。。
这个不会超时嘛?
埃氏筛,nlogn