求助巨佬!优化的素数判断写法没懂qwq
查看原帖
求助巨佬!优化的素数判断写法没懂qwq
751403
xzjxzjxzj楼主2023/8/3 23:06

萌新看到一篇题解后附有优化的素数判断写法,但......qwq

bool isprime(int n){
    if(n<=1) return false;
    if(n==2||n==3) return true;
    if(n%6!=1&&n%6!=5) return false;
    for(int i=5;i*i<=n;i+=6) if(n%i==0||n%(i+2)==0) return false;
    return true;
}

想问一下为什么需要

for(int i=5;i*i<=n;i+=6) if(n%i==0||n%(i+2)==0) return false;

这个代码

即:为什么不是

	if(x==1)
		return 0;
	else if(x==2||x==3)		
		return 1;
	else if(x%6!=1&&x%6!=5)
		return 0;
	return 1;

求助巨佬!跪谢

2023/8/3 23:06
加载中...