欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

判断质数的几种方法

程序员文章站 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]乘以某个数筛掉
    } 
  } 
}