題目在 https://zerojudge.tw/ShowProblem?problemid=b513
我先挑選這題來做基本的質數判斷. 以後有一堆質數的試題都可以用這題的程式來改.
我只用兩招來判斷質數就夠快了. 第一招是除了2和3這兩個質數外, 只判斷6n-1和6n+1的數, 其他的都不可能是質數. 第二招就是只用不大於sqrt(n)的質數來判斷n的餘數是不是0,只要有一個不是0, 那n就不是質數.
vector <int> V; //儲存所有質數
//判斷V是不是質數
bool getNextPrime(int v){
int max=sqrt(v);
for(int i : V){
if(i>max) break;
if(v%i==0)
return false;
}
return true;
}題目是要求n<=65535的數, 所以我們用第二招先求出n<=sqrt(65536)的所有質數就夠用了.
//求出<=n的所有質數
int n=sqrt(65535);
V.push_back(2);
V.push_back(3);
int index=6;
while(index-1<=n){
//判斷6n-1是不是質數
if(getNextPrime(index-1))
V.push_back(index-1);
//判斷6n+1是不是質數
if(index+1<=n){
if(getNextPrime(index+1))
V.push_back(index+1);
}
index+=6;
}完整的程式如下.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
vector <int> V; //儲存所有質數
//判斷V是不是質數
bool getNextPrime(int v){
int max=sqrt(v);
for(int i : V){
if(i>max) break;
if(v%i==0)
return false;
}
return true;
}
int main(){
//求出<=n的所有質數
int n=sqrt(65535);
V.push_back(2);
V.push_back(3);
int index=6;
while(index-1<=n){
//判斷6n-1是不是質數
if(getNextPrime(index-1))
V.push_back(index-1);
//判斷6n+1是不是質數
if(index+1<=n){
if(getNextPrime(index+1))
V.push_back(index+1);
}
index+=6;
}
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
if(getNextPrime(x))
printf("Y\n");
else
printf("N\n");
}
}