蓝桥杯之找素数(填空题+编程题)

这篇具有很好参考价值的文章主要介绍了蓝桥杯之找素数(填空题+编程题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 强烈推荐先看一下这篇蓝桥杯之素数及相关判断方法(看这一篇就够了)_冷兮雪的博客-CSDN博客

目录

一、找素数(填空题)

 1、题目

 2、题目解读

 3、代码

 二、找素数(编程题)

1、题目

2、题目解读 

 3、代码

一、找素数(填空题)


找素数 - 蓝桥云课 (lanqiao.cn)

 1、题目

题目描述

本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。

素数就是不能再进行等分的整数。比如:7,117,11。而 99 不是素数,因为它可以平分为 33 等份。一般认为最小的素数是22,接着是 3,5,...3,5,...

请问,第 100002100002(十万零二)个素数是多少?

请注意:“2” 是第一素数,“3”是第二个素数,依此类推。

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

 2、题目解读

看题目就是让我们找到第100002个素数,题目所给的最大运行时间为1s,可以使用任意一种找素数的方法。 看了我之前那篇文章就知道,有关找寻素数的方法有五种,那我就用这道题目来让大家直观明了的比较比较其中三种方法运行速度。

 3、代码

public class 找素数tkt {
    //欧拉筛法(埃氏筛法的优化版)
    public static void eulerSieve(int n){
        boolean[] isPrime = new boolean[50*n];
        int[] Prime=new int[n];//存放素数的数组,false为素数
        isPrime[0] = isPrime[1] = true;//数字0和1都不是素数,所以赋true
        int count = 0;

        for (int i = 2; i <50*n; i++) {
            if (count==100002)
                break;
            if (!isPrime[i])//若当前数是素数
                Prime[count++] = i;//则存入素数数组
            for (int j = 0; j < count && Prime[j] * i < 50*n; j++) {
                isPrime[i * Prime[j]] = true;
                if (i % Prime[j] == 0)
                    break;//避免重筛,使得程序更有效率
            }
        }
        System.out.println(Prime[count-1]);
    }
    //埃氏筛法
    static void isPrime(int n) {
        int[] b=new int[50*n];//通过数组b的值,为1就是素数
        int[] a=new int[n];//通过数组b的值,为1就是素数
        int p=0;//记录素数个数
        for(int i=0;i<50*n;i++)
            b[i]=1;
        b[0]=0;
        b[1]=0;
        //准备完毕
        for(int i=2;i<50*n;i++){
            if (p==100002)
                break;
            if(b[i]!=0){
                a[p++]=i;
                for(int j=2*i;j<50*n;j+=i)
                    b[j]=0;//剔除倍数
            }
        }
        System.out.println(a[p-1]);
    }
    //普通筛法
    static boolean check(int n) {
        for(int i=2;i<=n/i;++i) {
            if(n%i==0) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        long startTime1 = System.currentTimeMillis(); //获取开始时间
        int ans=0;
        int i=2;
        for(;i<50*100002;++i) {
            if(check(i)) ans++;
            if(ans==100002) break;
        }
        System.out.println(i);
        long endTime1 = System.currentTimeMillis(); //获取结束时间
        System.out.println("普通方法运行时间:" + (endTime1 - startTime1) + "ms"); //输出程序运行时间:280ms

        System.out.println("*********************");

        long startTime2 = System.currentTimeMillis(); //获取开始时间
        eulerSieve(100002);//1 299 743
        long endTime2 = System.currentTimeMillis(); //获取结束时间
        System.out.println("欧拉筛法运行时间:" + (endTime2 - startTime2) + "ms"); //输出程序运行时间:20ms

        System.out.println("*********************");

        long startTime3 = System.currentTimeMillis(); //获取开始时间
        isPrime(100002);//1 299 743
        long endTime3 = System.currentTimeMillis(); //获取结束时间
        System.out.println("埃氏筛法运行时间:" + (endTime3 - startTime3) + "ms"); //输出程序运行时间:50ms
    }
}

蓝桥杯之找素数(填空题+编程题)

 可以通过三种代码的运行速度一目了然看出欧拉筛法不是快的一丁半点,所以当题目数据过大或者运行限制更小时,我们应该尽量使用欧拉筛法去降低我们代码的运行时间。

 二、找素数(编程题)

1、题目

题目描述

给定一个区间 [a,b],请你求出该区间内有多少个素数。

输入描述

输入共一行,包含两个整数 a,b。

2≤a≤b≤2147483647,b−a≤10000002

输出描述

输出一个整数,表示答案。

输入输出样例

输入

2 6

输出

3

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

2、题目解读 

 题目要求我们找出区间[a,b]中有多少个素数,可以看到题目所给的a,b范围很大,而且

b-1<=10000002。这样我们简单的设数组,然后去使用前面的找素数的方法,就不行了,会超时,我们就需要在原来的方法上面进行改进。

如下面,就算是使用最快的欧拉筛法最后一个用例也会超时。所有在实际问题中也要学会创新,寻找到对应的解决方法。

蓝桥杯之找素数(填空题+编程题)


import java.util.*;

public class Main {
    public static final int MAX=1000005;
    public static boolean isprime[]=new boolean[MAX];
    public static boolean primelist[]=new boolean[MAX];

    public static int seg_sieve(int a,int b) {
        boolean[] isPrime = new boolean[b + 1];
        int[] Prime = new int[b];//存放素数的数组,false为素数
        isPrime[0] = isPrime[1] = true;//数字0和1都不是素数,所以赋true
        int count = 0;
        int x=0;
        for (int i = 2; i < b + 1; i++) {
            if (!isPrime[i]) {
                Prime[count++] = i;//则存入素数数组
                if (i>=a)
                    x++;
            }
                for (int j = 0; j < count && Prime[j] * i < b + 1; j++) {
                    isPrime[i * Prime[j]] = true;
                    if (i % Prime[j] == 0)
                        break;//避免重筛,使得程序更有效率
            }
        }
        return x;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int k = seg_sieve(a,b);

        System.out.println(k);
    }
}

 3、代码

 在开头说的文章中不必一直循环到n-1,因为如果a*b=n,则其中必有一个大于sqrt(n) ,一个小于sqrt(n),,所以我们把循环范围缩小到√n所以我们可以创建两个数组,用来分别标记[2,√n]中的素数,另一个数组用来标记[a,b]中的素数。找到在[2,√n]中的素数,然后去[a,b]数组中找这个素数的倍数,判定其不是素数,把[2,√n]中的素数遍历完,[a,b]数组中的素数也都找出来了。

import java.util.Scanner;

public class Main{
    static int N = 1000005;
    static boolean vis[] = new boolean[N];//标记[2,√b]中的素数
    static boolean PrimeN[] = new boolean[N];//标记[a,b]中的素数

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        PrimeN_sieve(a, b);
    }

    static void PrimeN_sieve(int x, int y) {
        for (int i = 2; i <= Math.sqrt(y); i++) {
            if (!vis[i]) {

//标记[2,√b]中的素数
                for (int j = i * i; j < Math.sqrt(y); j += i) {
                    vis[j] = true;
                }
//标记[a,b]中的素数
//Math.max(2, (a - 1 + i) / i) * i是找到大于a的第一个i的倍数,然后+i,把所有[a,b]
//中i的倍数都遍历一遍
                for (int k = Math.max(2, (x + i - 1) / i) * i; k < y + 1; k += i) {
                    PrimeN[k - x] = true;
                }
            }
        }
//计算出[a,b]中素数的个数
        int num = 0;
        for (int q = 0; q <= y - x; q++) {
            if (!PrimeN[q]) {
                num++;
            }
        }
        System.out.println(num);
    }
}

                                          蓝桥杯之找素数(填空题+编程题)文章来源地址https://www.toymoban.com/news/detail-416997.html

到了这里,关于蓝桥杯之找素数(填空题+编程题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯之“砝码称重“解题思路,含图解(Java)

    问题描述 你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W_1, W_2, · · · , W_N。 请你计算一共可以称出多少种不同的重量? 注意砝码可以放在天平两边。 输入格式 输入的第一行包含一个整数 N。 第二行包含 N 个整数:W_1, W_2, W_3, · · · , W_N​。 输出格式 输出一个整数

    2023年04月09日
    浏览(44)
  • 前端vscode必备插件(强烈推荐)

    目录 一、前言 二、工具推荐 1.《Chinese (Simplified) (简体中文) Language》 2.《ESLint》 3.《Git History》 4.vscode-icons  5.Path Intellisense 6.《Vetur》 7.《GitLens — Git supercharged》 8.《Image preview》 9.Debugger for Chrome 10.Prettier 11.AnyRule  13.Vue Language Features (Volar) 14.Vite 15.Code Spell Checker 16.Error Lens

    2024年02月06日
    浏览(65)
  • python做界面,强烈推荐nicegui

    在网上搜索 “python 做界面” ,得到的结果无非是 Tkinter 、 wxWidgets 、 Qt 、 Gtk 。它们要不然就是打包后太大,要不就是界面丑,要不就是代码繁琐。这些都是 GUI,那么 web 界面又如何? 我之前推荐过 streamlit,在简单的场景下,它仍然值得推荐。但是 streamlit 实在不灵活,受

    2024年02月13日
    浏览(36)
  • IDEA强烈推荐的TOP14插件

    最近家里组装了一台台式机,各种开发环境必不可少,在安装IDEA之后,就开始盘点之前MacBook上安装的各个好用的插件。 1. Background Image Plus 设置IDEA的背景图片,View -- set Background Image,选择背景图片 效果图: 2. Grep Console 可以根据表达式,对控制台的打印日志设置不同的背景

    2024年02月08日
    浏览(39)
  • 程序员强烈推荐:IDEA 常用配置指南

    1.1 基本配置 图 1.1-1 修改更改主题 + 背景图片 如果IDEA版本是2023.1.2以后的版本可以开启 newUI 体验新版的UI界面,我个人是挺喜欢的🌝 1.2 快捷键配置 图1.2-1 修改快捷键 2.1 配置GIT 图2.1-1配置git 【git提交的几个小建议】 建议对git提交人和提交信息进行规范,同时代码提交应当

    2024年02月09日
    浏览(70)
  • .Net全网最简RabbitMQ操作【强烈推荐】

    【前言】 本文自1年前的1.0版本推出以来,已被业界大量科技公司采用。同时也得到了.Net圈内多位大佬的关注+推荐,文章也被多家顶级.Net/C#公众号转载。 现在更新到了7.0版本,更好的服务各位.Neter。   【正文】 支持.Net/.Net Core/.Net Framework,可以部署在Docker, Windows, Linux, Ma

    2024年02月08日
    浏览(48)
  • 运维:18工作中常用 Shell 脚本, 强烈推荐

      1、检测两台服务器指定目录下的文件一致性

    2024年02月14日
    浏览(41)
  • 蓝桥杯官网填空题(平方末尾)

    题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 能够表示为某个整数的平方的数字称为“平方数” 虽然无法立即说出某个数是平方数,但经常可以断定某个数不是平方数。 因为平方数的末位只可能是:[0,1,4,5,6,9] 这 6 个数字中的

    2024年02月09日
    浏览(53)
  • 蓝桥杯官网填空题(距离和)

    题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 两个字母之间的距离定义为它们在字母表中位置的距离。例如 A 和 C 的距离为 2,L 和 Q 的距离为 5。 对于一个字符串,我们称字符串中两两字符之间的距离之和为字符串的内部

    2024年02月09日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包