前提
这题既然名为质数判定,肯定要用到质数的判定。质数怎么判定?让我们回归定义。质数,就是一个大于,且除了和它本身外,不能被其他自然数整除的自然数,用代数符号来说来说,设为质数,则,同时为整数,且不能在内(本身除外)的整数整除。
思路
既然为质数,那在内(本身除外)的整数就无法整除它,假设可以整除它,那么。所以循环节如下:
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