以下代码可以提速吗？
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的素性测试，你遇到的不可打表的素数验证题基本都可以过。如果你的思路没问题的话。。）
推荐阅读：
