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是素数，记为PRIM0
根据PRIM0，PRIM1，...PRIMK，寻找比PRIMK大的最小素数PRIMK+1（这里是根据素数找素数）
如果PRIMK+1大于N，则PRIMK是我们需要找的素数，否则继续寻找
枚举：
从可能的集合中一一列举各元素
根据所知道的知识，给一个猜测的答案
比如：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
3.采用合适的搜索顺序
搜索空间的遍历顺序要与模型中条件表达式一致 枚举关键字（枚举核心）： 减少规模 实例代码： 感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
例如：对{2,2*i+1|1<=i,2*i+1
#include