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

        3. 采用合适的搜索顺序

            搜索空间的遍历顺序要与模型中条件表达式一致
            例如：对{2,2*i+1|1<=i,2*i+1

    枚举关键字（枚举核心）：

        减少规模

实例代码：

#include 
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=2;i--){
    if(isPrimMothed(i)) return i;
  } 
}
int main(){
  int n;
  scanf("%d",&n);
  //int ans=primLessN(n);
  int ans=primLessN_2(n);
  cout<

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！