数据结构(二)-求<=N的最大素数

逃离我推掉我的手 2023-08-17 16:18 106阅读 0赞

Q:求解小于或等于整数N的最大素数

A：穷举法枚举从N到√N，逐个用2到√N的数去整除，若能除尽则不是素数。

tips：如果一个整数N不是素数，它一定可以分解为比它小的两个整数的乘积，其中一个乘数小于或等于根号n，另一个大于或等于根号n。

怎么证明最大素数一定在根号n到n之间出现？

[A：伯特兰-切比雪夫定理][A_-]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//根号n到n的每一个数的因数范围都可以被n的判断范围所覆盖
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    
    int main(){
        int n;
        cin>>n;
        int d=(int) sqrt(n);//d：边界
        for(int i=n;i>=d;i-- ){
         //从大到小逐一检查
            int j;
            for( j=2; j<=d; j++){
                if(i%j == 0) break;
            }
            if(j > d) {printf("%d\n",i); break;}
        }
        return 0;
    }

后记：算法解题的策略和数学思想方法很有联系。

比如迭代法求二次方程的根；渐次逼近思想。

简单性原理来分解问题，以简驭繁

转载于:https://www.cnblogs.com/SUMaywlx/p/11520069.html

[A_-]: https://baike.baidu.com/item/%E4%BC%AF%E7%89%B9%E5%85%B0-%E5%88%87%E6%AF%94%E9%9B%AA%E5%A4%AB%E5%AE%9A%E7%90%86
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/e2bca7f490a84f7e9edf0c9cdba78d6e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构(二)-求<=N的最大素数

Q:求解小于或等于整数N的最大素数 A：穷举法枚举从N到√N，逐个用2到√N的数去整除，若能除尽则不是素数。 tips：如果一个整数N不是素数，它一定可以分解为比它小的两个

逃离我推掉我的手/ 2023年08月17日 16:18/ 0 赞/ 107 阅读

相关 #数据结构求二叉树的最小深度

//求二叉树根结点到叶子结点的最小深度 int minDepth(struct TreeNode\ root)\{ if(root==NULL)\{ return

末蓝、/ 2023年02月17日 03:22/ 0 赞/ 61 阅读

相关编程计算n(2＜=n＜=500)以内的10个最大素数及其和，分别输出这最大的10个素数及其和

题目内容：编程计算n(n<=500)以内的10个最大素数及其和，分别输出这最大的10个素数及其和。n的值要求从键盘输入。要求10个素数按从大到小的顺序输出。程序运行示例

Love The Way You Lie/ 2023年01月16日 06:47/ 0 赞/ 214 阅读

相关求n以内的所有素数并输出

include<stdio.h> include<stdlib.h> include<math.h> //求n以内的所有素数 int

迷南。/ 2022年08月07日 11:58/ 0 赞/ 258 阅读

相关快速求小于N的所有素数

首先，贴上实现的源代码： // // main.cpp // testC++1 // // Created by fei dou

我会带着你远行/ 2022年06月08日 01:07/ 0 赞/ 272 阅读

相关 JavaScript求n个数的最大值

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</

╰+攻爆jí腚メ/ 2022年05月20日 02:57/ 0 赞/ 257 阅读

相关求1-N之间的素数

一、什么是素数：素数（prime number）又称质数，有无限个。一个大于1的自然数，除了1和它本身外（因为1既不是素数，也不是合数），不能被其他自然

我不是女神ヾ/ 2022年05月18日 03:52/ 0 赞/ 247 阅读

相关输入一个自然数n，求小于等于n的素数之和？

问题描述：输入一个自然数n，求小于等于n的素数之和；例如：样例输入：2 样例输出：2。解题思路：（1）什么是素数：素

痛定思痛。/ 2022年05月17日 11:38/ 0 赞/ 354 阅读

相关 1.1 小于n的最大素数，完美立方

求小于n的最大素数（筛选法） ![70][] ![70 1][] include<iostream> include<cstring> defin

Love The Way You Lie/ 2022年05月11日 00:26/ 0 赞/ 206 阅读

相关用简单素数筛选法求N以内的素数

import java.util.Scanner; public class Main \{ public static void main(String\[\] ar

￡神魔★判官ぃ/ 2022年05月04日 20:50/ 0 赞/ 328 阅读