C++如何判断素数
C++ 如何 判断 素数
2023-09-27 14:27:35 时间
素数又称为质数,是指除了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楼▼
人必须要有主见,其次学会拒绝,不要怕尴尬不好意思,拒绝会让人很轻松。不愿意的事情一旦答应了就会后悔,拒绝很简单,勇敢说不——“不好意思,我不需要,我还有其他事情要做。”
相关文章
- 引用与指针:在C++中如何做出正确的选择?
- 【数据库开发】如何创建MySQL数据库连接池(一个基于libmysql的MySQL数据库连接池示例(C/C++版))
- C++ 引用 指针 使用举例
- C++总的const使用说明
- C++:函数先声明后实现
- C++中如何精确地输出特定类型的位数
- java如何去调用C++的方法详解
- 最常用的两种C++序列化方案的使用心得(protobuf和boost serialization)
- c++ JSON class:Value、Reader、Writer。jsoncpp
- Effective C++ (五)实现
- Error: Your project contains C++ files but it is not using a supported native build system.Consider
- c/c++中宏定义##连接符 和#符的使用
- c++读写文件和测试程序运行时间的例子
- [c/c++]3.如何查看和更改程序运行栈的大小
- 混合编程:如何用pybind11调用C++
- vs 2017/2015/2013 如何定位C++内存泄漏
- VC++非MFC项目中如何使用TRACE宏
- c++性能之map实现性能比较
- DevC++编译器
- 2018-8-10-如何入门-C++-AMP-教程
- 2018-8-10-如何入门-C++-AMP-教程
- 如何入门 C++ AMP 教程
- 如何在Ubuntu中使用Eclipse + CDT开发C/C++程序
- 【C++11 多线程】原子操作(六)
- C++:函数重载和模板函数之间的问题 | 完美转发的概念
- 在linux下如何编译C++程序
- Linux教程:如何在Linux下进行C++开发?