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
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

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

#include<iostream>
#include<math.h>
using namespace std;
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是素数 
}
int main(){
	for(int i=2;i<100;i++){//从2开始遍历到100
		if(isPrime(i))//如果是素数则输出
			cout<<i<<" ";
	}
	return 0;
} 

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

第5012楼
▼
人必须要有主见，其次学会拒绝，不要怕尴尬不好意思，拒绝会让人很轻松。不愿意的事情一旦答应了就会后悔，拒绝很简单，勇敢说不——“不好意思，我不需要，我还有其他事情要做。”

文章来源: blog.csdn.net，作者：振华OPPO，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_42257666/article/details/114239664