C++如何判断素数

振华OPPO 发表于 2022/04/22 15:17:14 2022/04/22
【摘要】 素数又称为质数,是指除了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都不...

素数又称为质数,是指除了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以内的素数,完整程序如下:

#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;
} 

第5012楼

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。