C++如何判断素数

素数又称为质数，是指除了1和本身之外，不能被其他数整除的一类数。即对给定的正整数n，如果对任意的正整数a（1<a<n），都有n%a!=0成立，那么称n是素数；否则，如果存在a(1<a<n)，使得n%a==0，那么称n为合数。应特别注意的是，1既不是素数，也不是合数。

从素数的定义中，我们可以知道，一个整数m要被判断为素数，需要判断n是否能被2、3…n-1中的一个整除，只有2,3，…,n-1都不能整除n,n才能判定为素数，而只要有一个能整除n的数出现，n就可以判定为非素数。

这样的判定方法没有问题，时间复杂度为O(n)，但可以优化，因为如果k是n的一个约数，那么n/k也是n的一个约数，k和n/k必然满足，一个小于等于sqrt（n），另一个大于等于sqrt(n)，其中sqrt(n)为根号n。所以只要判断n是否能被2,3…sqrt(n)中的一个数整除，即可判定n是否为素数，时间复杂度为O(sqrt(n))。

代码如下：

bool isPrime(int n){
  if(n<=1) return false;//特判
  int sqr=(int)sqrt(n);//根号n
  for(int i=2;i<=sqr;i++){//遍历2~根号n 
  if(n%i==0) return false;//n是i的倍数，则n不是素数 
  } 
  return true;//n是素数 
}

如果查询1~100以内的素数，完整程序如下：

bool isPrime(int n){
  if(n<=1) return false;//特判
  int sqr=(int)sqrt(n);//根号n
  for(int i=2;i<=sqr;i++){//遍历2~根号n 
  if(n%i==0) return false;//n是i的倍数，则n不是素数 
  } 
  return true;//n是素数 
}