个人中心
gpt4 book ai didi

C++ 实现求小于n的最大素数的实例

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章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}，按照从小到大的顺序            。

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

        减少规模 。

实例代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#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;
}

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

原文链接：http://www.cnblogs.com/Renyi-Fan/p/6922940.html 。

最后此篇关于C++ 实现求小于n的最大素数的实例的文章就讲到这里了,如果你想了解更多关于C++ 实现求小于n的最大素数的实例的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

24 4 0
文章推荐： 虚拟主机买哪种的好？
文章推荐： C++ 中CloseHandle 函数--关闭一个句柄
文章推荐： C++ 中回文数判断简单实例
文章推荐： 老生常谈C/C++内存管理
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com