本題我曾想以[1,500000]內的質因子為基礎來判定整個int范圍的質數，但是超時。 無奈用Miller Rabin算法吧。 根據 ：費爾馬小定理，如果 n 為素數，那麼對於小於n的數a有a^(n-1) = 1(mod n) 那麼我們可以隨機生成一個a（a<n），如果滿足a^(n-1) = 1(mod n),那麼n就有可能是質數。隨機生成三次，即驗證三次，那麼這個概率就非常大。 關於a^b%n，用快速冪來解。 [cpp] #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> using namespace std; long long mul(long long a,long long b) { return a * b; } long long power(long long a,long long b,int n) { //快速冪取模a^b%n long long b_temp = b; long long result = 1; while(b_temp) { if(b_temp&1) { result = mul(result,a)%n; } a = mul(a,a)%n; b_temp = b_temp>>1; } return result; } bool Miller_Rabbin(long long n) { //費爾馬小定理，如果 n 為素數，那麼對於小於n的數a有a^(n-1) = 1(mod n) long long a = rand()%(n-1)+1;//隨機生成一個小於n的數 //a^(n-1) = 1(mod n) if(power(a,n-1,n)!=1) { return false; } return true; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif long long n; while(scanf("%lld",&n)!=EOF) { int flag = 1;//1表示素數 int times = 3;//times為每個數進行測試的次數 if(n<=1) { flag = 0; } else if(n==2||n==3) { flag = 1; } else { while(times--&&flag) { if(!Miller_Rabbin(n)) { flag = 0; } } } if(!flag) { printf("NO\n"); } else { printf("YES\n"); } } return 0; }
