題目在 https://zerojudge.tw/ShowProblem?problemid=a007
這題難度在質數範圍廣2 ≦ x ≦ 2147483647, 測資多到20萬筆. 我看他AC比率不到兩成.
其實2147483647就是2的31次方, 開方後46340, 求出小於46340的質數也還好, 請參考另一篇zerojudge b513. 判斷質數-商競103有詳細解釋,用相同的方法也夠快了. 程式用另一篇zerojudge a626. 6. Prime Directive來改參數範圍.
完成程式如下.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
//V儲存所有的質數
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(){
//求出小於等於sqrt(2147483647)的所有質數
int n=sqrt(2147483647);
V.push_back(2);
V.push_back(3);
int index=6;
while(index-1<=n){
if(getNextPrime(index-1))
V.push_back(index-1);
if(index+1<=n){
if(getNextPrime(index+1))
V.push_back(index+1);
}
index+=6;
}
//依測資要求檢查x是否為質數
int x;
while(scanf("%d",&x)!=EOF)
{
if(getNextPrime(x))
printf("質數\n");
else
printf("非質數\n");
}
}