判断质数的几种方法
程序员文章站
2024-03-15 14:45:35
...
思路借鉴(https://www.cnblogs.com/xiehongfeng100/p/4332998.html)
1:若不知道范围
num =√num*√num。 如果n除以大于√num的数,必得到小于√num的商,而小于√num的整数已经在2到√num的整数试过了,没有必要再试(√num, num)范围内的数了,再去掉偶数的情况,除2外的偶数都不是质数
bool judge(int num)
{
if(num==2)
return true;
if(num%2)
{
for(int i=2;i<(sqrt(num)+1);i++)//+1 例 num=6,i=3;
if(!(num%i)) //注意 里面要加括号
return false;
return true;
}
return false;
}
2:知道范围——欧拉筛
const int N=10000000;
int pr[N+1],top=0;
bool b[N+1];
void prime(int n)
{
top=0;
memset(b,1,sizeof(b));
b[0]=0;b[1]=0;
for (int i=2;i<=n;i++)
{
if (b[i])////不是目前找到的素数的倍数
pr[++top]=i;//找到素数
for (int j=1;j<=top&&pr[j]*i<=n;j++)
{
b[pr[j]*i]=0; //找到的素数的倍数不访问
if (i%pr[j]==0) break; //这句话的意思就是说,因为如果pr[j]|i了,说明i*pr[j+1]肯定会被pr[j]乘以某个数筛掉
}
}
}