以下代碼可以提速嗎？
inline int zh(uint_fast64_t x)
{
if (x%2==0) return x==2;
uint_fast64_t y = 3;
for (y = 3; y &<= x / 2; y+=2) { if (x%y==0) { return 0; } } return 1; }這是一個判斷一個數是不是質數的函數，是質數返回1，不是質數返回0。有辦法再加快其速度嗎？最好提供更好的演算法（題主初中生，高等數學可能聽不懂，求大神指點）
推薦BPSW演算法
這是Pari/GP的偽素數測試的說明：
ispseudoprime(x,{flag}): true(1) if x is a strong pseudoprime, false(0) if not. If flag is 0 or omitted, use BPSW test, otherwise use strong Rabin-Miller test for flag randomly chosen bases.
在Pari/GP的文檔裏，可以清楚地看到：
There are no known composite numbers passing the above test, although it is
expected that infinitely many such numbers exist. In particular, all
composites are correctly detected
也就是，這個演算法可以完成你的全部需求。
"y &<= x/2"換成"y &<= sqrt(x)"
定義函數p使得：
然後：
或者： inline int zh(uint_fast64_t x)inline int zh(uint_fast64_t x)
{
int n=1;
while(p(++n)&
int factorial(uint_fast64_t x)
{
if(x=0)
return 1;
return x*factorial(x-1);
}
{
if((factorial(x-1)+1)%x==0)
return 1;
return 0;
}
狗頭
正經做法是將y&<=x/2改成y&<=sqrt(x)，因為如果正整數x是合數，則總是存在因子 使得
。
首先，數據類型不要亂用。uint_fast64_t這個沒有平臺統一標準。
然後，做一個簡單的優化，將y/2換成sqrt(y)，這樣可以對複雜度進行降階為O(√n)，因為要遍歷的次數大大降低了。
最後，進一步的優化，我們觀察一下關於質數分佈的規律：大於等於5的質數一定和6的倍數相鄰。例如5和7，11和13,17和19等等，這樣我們可以將複雜度中的常數項降低，變為O(1/3√n) ，代碼如下:
int IsPrime(int n)
{
double n_sqrt;
if(n == 2 || n == 3) return 1;
if(n % 6 != 1 n % 6 != 5) return 0;
n_sqrt=floor(sqrt((double)n));
for(int i = 5; i &<= n_sqrt; i += 6){
if(n % i==0 | n % (i+2) == 0) return 0;
}
return 1;
}
如果答主是要得到1-n中所有的質數，用歐拉篩法就行了，時間複雜度為O(n)，比遍歷+判斷函數的時間複雜度O(n√n)快多了。
const int maxn=100000001;
int prime[maxn]; //素數表
bool sf[maxn]; //判斷這個數是不是素數，sf[i]中的i是從1到maxn的數
void GetPrime(){ //核心 歐拉篩代碼
int num=0; //num 用來記篩到第幾個質數
memset(sf,true,sizeof(sf));
for(int i=2;i&<=maxn;i++){ //外層枚舉1~maxn
if(sf[i]) prime[++num]=i; //如果是質數就加入素數表
for(int j=1;j&<=num;j++){ //內層枚舉num以內的質數
if(i*prime[j]&>maxn) break; //篩完結束
sf[i*prime[j]]=false; //篩掉...
if(i%prime[j]==0) break; //避免重複篩
}
}
sf[1]=false;
sf[0]=false; //1 0 特判
}
可以考慮Miller rabin素數測試演算法，如果枚舉因數的話速度最快 ，這個演算法雖然有幾率出錯（出錯率很小，基本不可能），時間複雜度為
該演算法基於費馬小定理（可以看看歐拉定理）和二次探測
即如果p是質數， 。
的解為
或
通過一定的演算法（這個自己百度）多次進行二次探測和費馬小定理檢測，可以基本確定 是否為素數
具體代碼實現樓下也有人說了
如果要找幾百萬甚至上億以內的所有素數，也許可以考慮一下歐拉篩，時間複雜O(n)。
歐拉篩的模板
prime[]數組中的素數是遞增的,當i能整除prime[j]，那麼i*prime[j+1]這個合數肯定被prime[j]乘以某個數篩掉。
因為i中含有prime[j],prime[j]比prime[j+1]小，即i=k*prime[j]，那麼i*prime[j+1]=(k*prime[j])*prime
[j+1]=k』*prime[j]，接下去的素數同理。所以不用篩下去了。因此，在滿足i%prime[j]==0這個條件之前以及第一次
滿足改條件時,prime[j]必定是prime[j]*i的最小因子。
bool number[maxn+5];
void isprime()
{
int prime[maxn+5];
int i,j,c=0;
memset(number,true,sizeof(number));
for(i=2;i&<=maxn;i++)
{
if(number[i])
prime[c++]=i;
for(j=0;j&
{
number[prime[j]*i]=false;
if(i%prime[j]==0) //保證每個合數只會被它的最小質因數篩去，因此每個數只會被標記一次
break;
}
}
}
摘自網路。
知乎怎麼敲代碼呀，還是MD方便
提不提速先不說，zh(2)返回的是啥？
看到有人在考慮篩法算素數，而題主只在意數是否為素數。。
經典演算法的話，判斷一個數是否為素數的複雜度是 的。（y的上界設為
）
但對於一個比較大的素數而言，我殘存的演算法競賽知識告訴我應該是大於1e16的時候，你再用經典演算法來算，一般的題就會TLE了。。
所以這個時候你可以採用米勒拉賓演算法~（下面是演算法模板），但米勒拉賓演算法並不能一定保證結果的正確性，它出錯的概率是 。
#define LL long long
#define range(i,a,b) for(auto i=a;i&<=b;++i)
const int S=20;
LL mult_mod(LL a,LL b,LL c){
a%=c;
b%=c;
long long ret=0;
while(b){
if(b1){ret+=a;ret%=c;}
a&=c)a%=c;
b&>&>=1;
}
return ret;
}
LL pow_mod(LL x,LL n,LL mod){
if(n==1)return x%mod;
x%=mod;
LL tmp=x;
LL ret=1;
while(n){
if(n1) ret=mult_mod(ret,tmp,mod);
tmp=mult_mod(tmp,tmp,mod);
n&>&>=1;
}
return ret;
}
bool check(LL a,LL n,LL x,LL t){
LL ret=pow_mod(a,x,n);
LL last=ret;
range(i,1,t){
ret=mult_mod(ret,ret,n);
if(ret==1last!=1last!=n-1) return true;
last=ret;
}
if(ret!=1) return true;
return false;
}
bool Miller_Rabin(LL n){
if(n&<2)return false;
if(n==2)return true;
if((n1)==0) return false;
LL x=n-1;
LL t=0;
while((x1)==0){x&>&>=1;t++;}
range(i,0,S-1){
LL a=rand()%(n-1)+1;
if(check(a,n,x,t))return false;
}
return true;
}
LL factor[100];
int tol;
LL gcd(LL a,LL b){
if(a==0)return 1;
if(a&<0) return gcd(-a,b);
while(b){
long long t=a%b;
a=b;
b=t;
}
return a;
}
LL Pollard_rho(LL x,LL c){
LL i=1,k=2;
LL x0=rand()%x;
LL y=x0;
while(1){
i++;
x0=(mult_mod(x0,x0,x)+c)%x;
LL d=gcd(y-x0,x);
if(d!=1d!=x) return d;
if(y==x0) return x;
if(i==k){y=x0;k+=k;}
}
}
void findfac(LL n){
if(Miller_Rabin(n)){
factor[tol++]=n;
return;
}
LL p=n;
while(p&>=n)p=Pollard_rho(p,rand()%(n-1)+1);
findfac(p);
findfac(n/p);
}
但是呢，在實際做題中，上面的C++演算法板子也有可能會TLE，所以你可以考慮使用Java自帶的米勒拉賓素性測試~
import java.math.BigInteger;
import java.util.Scanner;
class test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
BigInteger x = sc.nextBigInteger();
if (x.isProbablePrime(20)) System.out.println("Is prime");
else System.out.println("Not prime");
}
}
（利用Java的素性測試，你遇到的不可打表的素數驗證題基本都可以過。如果你的思路沒問題的話。。）
推薦閱讀：
