前提
这题既然名为质数判定，肯定要用到质数的判定。质数怎么判定？让我们回归定义。质数，就是一个大于，且除了和它本身外，不能被其他自然数整除的自然数，用代数符号来说来说，设为质数，则，同时为整数，且不能在内（本身除外）的整数整除。
思路
既然为质数，那在内（本身除外）的整数就无法整除它，假设可以整除它，那么。所以循环节如下：
int p;
bool Is_Prime = true;
cin >> p; // scanf("%d",&p);
for(int i = 2;;i++){
if(p % i == 0){
Is_Prime = false;//能被整除则不是质数
}
}
到这，请观察这一行
for(int i = 2;;i++)
循环无结束条件，会陷入死循环，所以我们要缩短i的范围。
假设，则恒成立，
∵，∴，∴在的情况下不可能存在。
那条件不就缩到了吗？注意：本身除外。
还有当我们已经知道有一个满足就可以结束循环了，所以
if(p % i == 0){
Is_Prime = false;
break;
}
这样节省了时间，所以总体代码如下：
#include<bits/stdc++.h>
using namespace std;
int t;
int main(){
cin >> t; //scanf("%d",&t);
while(t--){
int x;
cin >> x;
bool Is_Prime = true;
for(int i = 2;i < x;i++){
if(x % i == 0){
Is_Prime = false;
break;
}
}
if(Is_Prime){
cout << "Y" << endl;
}
else{
cout << "N" << endl;
}
}
return 0;
}
但提交发现，说明代码时间复杂度太大了，那么该如何减小时间复杂度呢？
显然从与已经无法下手，只有了。
那么怎么缩短的范围呢？
我们假设，那么则有，
∵，∴，∴，∴在的情况下不存在整数满足，∴。
具体代码如下：
#include<bits/stdc++.h>
using namespace std;
int t;
int main(){
cin >> t; //scanf("%d",&t);
while(t--){
int x;
cin >> x;
bool Is_Prime = true;
for(int i = 2;i <= x / 2;i++){
if(x % i == 0){
Is_Prime = false;
break;
}
}
if(Is_Prime){
cout << "Y" << endl; //printf("Y\n");
}
else{
cout << "N" << endl; //printf("N\n");
}
}
return 0;
}
测试结果：分。
那分去哪了？注意：不是质数。所以要对进行特判。
#include<bits/stdc++.h>
using namespace std;
int t;
int main(){
cin >> t; //scanf("%d",&t);
while(t--){
int x;
cin >> x;
bool Is_Prime = true;
for(int i = 2;i <= x / 2;i++){
if(x % i == 0){
Is_Prime = false;
break;
}
}
if(x == 1){
Is_Prime = false;
}
if(Is_Prime){
cout << "Y" << endl; //printf("Y\n");
}
else{
cout << "N" << endl; //printf("N\n");
}
}
return 0;
}
测试结果： 分。
到这里已经圆满结束，但是注意时间复杂度：！这个代码跑得太慢了，得提提速啊。
事实上，若存在，则也成立。所以假设，则。也就是说在内，则必有p/i的范围为。所以只用循环到即可。
答案
#include<bits/stdc++.h>
using namespace std;
int t;
int main(){
cin >> t; //scanf("%d",&t);
while(t--){
int x;
cin >> x;
bool Is_Prime = true;
for(int i = 2;i * i <= x;i++){
if(x % i == 0){
Is_Prime = false;
break;
}
}
if(x == 1){
Is_Prime = false;
}
if(Is_Prime){
cout << "Y" << endl; //printf("Y\n");
}
else{
cout << "N" << endl; //printf("N\n");
}
}
return 0;
}
测试结果： 分 。
当然用质数筛法效果更好。
结尾
质数筛法代码：
#include <bits/stdc++.h>
using namespace std;
int n, a[1000001], b[1000001], now = 1, len = 0;
int main() {
scanf("%d", &n); //cin >> n;
a[1] = 1;
for (int i = 1; i <= n; i++) {
int t;
scanf("%d", &t); //cin >> t;
if (now >= t) {
if (a[t] == 0) {
printf("Y\n"); //cout << "Y" << endl;
}
else {
printf("N\n"); //cout << "N" << endl;
}
}
else if (a[t] == 1) {
printf("N\n"); //cout << "N" << endl;
}
else {
for (int j = now + 1; j <= t; j++) {
if (a[j] == 0) {
b[++len] = j;
}
for (int k = 1; k <= len && j * b[k] <= 1000000; k++) {
a[j * b[k]] = 1;
if (j % b[k] == 0) {
break;
}
}
}
now = t;
if (a[t] == 0) {
printf("Y\n"); //cout << "Y" << endl;
}
else {
printf("N\n"); //cout << "N" << endl;
}
}
}
return 0;
}
测试结果： 分。可以尝试理解下。
共 9 条回复
...
谢啦
@fubohao2020 超时了，把 写成 或 就行了。
但是。。。老铁666啊
可能我电脑延迟了
100 166 ms
#include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while(t--) { int x; cin >> x; bool s=true; for(int i=2;i<x;i++) { if(x%i==0) { s=false; break; } } if(x==1) { cout<<"N"; continue; } if(s) { cout << "Y" << endl; } else { cout << "N" << endl; } } return 0; } 为什么我错了？？？？？？？？？
支持！
orz