C++ 实现求小于n的最大素数的实例
C++ 实现求小于n的最大素数的实例
枚举就是基于已有知识镜像答案猜测的一种问题求解策略
问题:求小于n的最大素数
分析:
找不到一个数学公式,使得根据N就可以计算出这个素数
我们思考:
N-1是素数么?N-2是素数吗?...
所以我们就是判断N-K是否为素数:
N-K是素数的充分必要条件:N-K不能被[2,n-k)中任何一个整除
判断N-K是否为素数的问题可以转化为:
求小于N-K的全部素数(求“小于N的最大素数”中的条件是“n不能被[2,n)中任意一个素数整除”,而不是整数)
不能被[2,n)中任意一个素数整除的数一定是素数,因为那些整数都是以素数为因子的,
所以没必要检测所有整数,检测所有素数就ok了
解决方法:
2是素数,记为PRIM 0
根据PRIM 0,PRIM 1,...PRIM K,寻找比PRIM K大的最小素数PRIM K+1(这里是根据素数找素数)
如果PRIM K+1大于N,则PRIM K是我们需要找的素数,否则继续寻找
枚举:
从可能的集合中一一列举各元素
根据所知道的知识,给一个猜测的答案
比如:2是素数,那2是本问题的解么
枚举算法:
对问题可能解集合的每一项:
根据问题给定的检验条件判断哪些是成立的
使条件成立的即为问题的解
枚举过程:
判断猜测答案是否正确
2是小于N的最大素数么?
进行新的猜测:
有两个关键因素要注意:
1. 猜测的结果必须是前面的猜测中没有出现过的。每次猜测的素数一定要比已经找到的素数大
2. 猜测的过程中要及早排除错误的答案。比如:除2之外,只有奇数才可能是素数
枚举过程中需要考虑的问题:
1. 给出解空间,建立简介的数学模型
可能的情况是什么?
模型中变量数尽可能的少(使规模尽量小),他们之间相互独立
求“小于N的最大素数”中的条件是“n不能被[2,n)中任意一个素数整除”
而不是“n不能被[2,n)中任意一个整数整除”
2. 减少搜索的空间
利用知识缩小模型中各变量的取值范围,避免不必要的计算
比如:较少代码中循环体执行的次数
除2之外,只有奇数才可能是素数,{2,2*i+1|1<=i,2*i+1<n}
3. 采用合适的搜索顺序
搜索空间的遍历顺序要与模型中条件表达式一致
例如:对{2,2*i+1|1<=i,2*i+1<n},按照从小到大的顺序
枚举关键字(枚举核心):
减少规模
实例代码:
#include <iostream> using namespace std; int prim[50000];//用来存所有素数 int primNum=0;//用来记录 prim数组中已经存入的素数的数量 int times=0; //用于记录求解问题的总共判断次数 int primLessN(int n); int primLessN_2(int n); bool isPrimMothed(int n); //判断一个数是否为素数 /* 方法一:由前往后用素数判断的枚举法: 求“小于N的最大素数”中的条件是“n不能被[2,n)中任意一个素数整除”,而不是整数 当n=10 0000时, ans=99991 times=4626 4478次 primNum=9592 我每一个素数被判断出来,都要遍历一下之前的素数表 而判断10 0000的时候,外层循环走了50000,里层每一个素数就是一次之前素数表的遍历 50000*(1+2+3+...+9592)=50000* 4600 8082 前面那个数没有50000,还要减去那些非素数 从 50000* 4600 8082可以看出,主要是之前那些素数花的时间,非素数几乎没花时间 非素数= 4626 4478-4600 8082= 25 6450 只有25万,虽然还是要比下面多很多,因为是从前往后比较的 */ int primLessN(int n) { prim[0]=2; //2是最小的素数 primNum++; for(int i=3;i<n;i+=2){ bool isPrim=1; //isPrim用来判断一个数是否为素数 for(int j=0;j<primNum;j++){ times++; if(i%prim[j]==0){ isPrim=0; break; //没加break之前, 当n=10 0000时,times=2 5239 6936次 (2.5亿) ,加了之后times=4626 4478次 (4.5千万次) } } if(isPrim) prim[primNum++]=i;//如果是素数,则存入prim素数数组 } return prim[primNum-1]; } /* 方法二: 由后往前的整数枚举法 而且方法二的空间消耗也少 当n=10 0000时, ans=99991 times=346次 当n=100 0000时,用方法一的话,根本算不出来 ans=99 9983 times=1811次 当n=1 0000 0000(一亿)时, ans=9999 9989 times=11314次 当n=10 0000 0000(十亿)时, ans=9 9999 9937 times=52537次 */ bool isPrimMothed(int n){ bool isPrim=1; //isPrim用来判断一个数是否为素数 if(n==2||n==3) return 1; for(int i=2;i*i<=n;i++){ times++; if(n%i==0) return 0; } return 1; } int primLessN_2(int n){ for(int i=n;i>=2;i--){ if(isPrimMothed(i)) return i; } } int main(){ int n; scanf("%d",&n); //int ans=primLessN(n); int ans=primLessN_2(n); cout<<ans<<endl; printf("总判断次数times:%d\n",times); printf("总素数数primNum:%d\n",primNum); return 0; }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25