*【每日一题 提高题】[蓝桥杯 2022 国 A] 选素数
选素数
小蓝有一个数 x,每次操作小蓝会选择一个小于 x 的素数 p,然后在 x 成为 p 的倍数前不断将 x 加 1,(如果 x 一开始就是 p 的倍数则 x 不变)。
小乔看到了小蓝进行了 2 次上述操作后得到的结果 n,他想知道 x 在一开始是多少。如果有多种可能,他想知道 x 一开始最小可以是多少,而如果不存在任何解,说明小乔看错了,此时请输出 −1。
输入格式
输入一行包含一个整数 n,表示经过两次操作后 x 的值。
输出格式
输出一行包含一个整数表示 x 的初始值。如果有多个解,输出最小的。如果不存在解,请输出 −1
这个题主要考察质因数分解和质数判断
首先质数的判断,这个太常见了,这里就不多赘述
private static boolean isPrime(int n){if (n<2)return false;if (n==2||n==3)return true;if (n%6!=1&&n%6!=5)return false;for (int i = 5; i*i<= n ; i+=6) {if (n%i==0||n%(i+2)==0){return false;}}return true;}
然后是质因数分解,这里用了 List 集合去装分解出来的质数
private static List<Integer> prime(int n){List<Integer> ans = new LinkedList<>();for(int i = 2; i <= n/i ; i++){//判断条件用n/i,以防i*i<=n发生溢出int a = 0;//每次循环都要清零while(n % i == 0){n /= i;a++;}if(a > 0)ans.add(i);}//若该数是质数,那么应该将自身(n)也加入if(n > 1) ans.add(n);return ans;}
最后就是根据题意进行模拟,a0→a1→ a2
(依次进行第一次操作、第二次操作)。
import java.util.*;//导入万能类 当然也不是很万能
public class Main {static List<Integer> oList = new LinkedList<>();//需要用到的集合public static void main(String[] args) {//标准输入 一个nScanner sc = new Scanner(System.in);int n = sc.nextInt();if (isPrime(n)){//如果输入数为质数,那么打印-1。因为我们的n应该是质数的倍数,且必须至少为2倍(题目中说了选择一个小于x的素数p,所以至少是2倍)。System.out.println("-1");}else {oList = prime(n);//对其质因数分解,并用集合装好int minstart = Integer.MAX_VALUE;//定义所求的最小开始的a0,赋值为Integer最大值,为了后面获取最小值for (int i = 0; i < oList.size(); i++) {//遍历质因数集合int last_left = n-oList.get(i);//下面对第一次操作后可能的数组遍历for (int j = last_left+1; j <= n ; j++) {//这里的范围为什么是从last_left+1到n//假设第二次操作选择的是oList.get(i)作为质数,那么第二次操作前的数(a1)不会小于n-oList.get(i)//上次操作前的数字(a1)必然在左边界加1和n之间。(为什么是n?因为n可能本身就是某个质数的倍数,然后这次操作又选了该质数,则n不变)if (isPrime(j)){continue;//跟上面一样,不可能是质数。}List<Integer> temp = prime(j);//继续对上个数进行质因数分解int max = Collections.max(temp);//找出最大的质因数作为第一次操作选择的质数,这样能使起始数字(即a0)尽可能小minstart = Math.min(j-max+1,minstart);//更新维护最小数字}}if (minstart==Integer.MAX_VALUE){System.out.println("-1");}else {System.out.println(minstart);}}}//质数的判断private static boolean isPrime(int n){if (n<2)return false;if (n==2||n==3)return true;if (n%6!=1&&n%6!=5)return false;for (int i = 5; i*i<= n ; i+=6) {if (n%i==0||n%(i+2)==0){return false;}}return true;}//对n进行质因数分解private static List<Integer> prime(int n){List<Integer> ans = new LinkedList<>();for(int i = 2; i <= n/i ; i++){//判断条件用n/i,以防i*i<=n发生溢出int a = 0;//每次循环都要清零while(n % i == 0){n /= i;a++;}if(a > 0)ans.add(i);}//若该数是质数,那么应该将自身(n)也加入if(n > 1) ans.add(n);return ans;}
}
相关文章:
*【每日一题 提高题】[蓝桥杯 2022 国 A] 选素数
选素数 小蓝有一个数 x,每次操作小蓝会选择一个小于 x 的素数 p,然后在 x 成为 p 的倍数前不断将 x 加 1,(如果 x 一开始就是 p 的倍数则 x 不变)。 小乔看到了小蓝进行了 2 次上述操作后得到的结果 n,他想…...
华为云环境下LVS/DR架构的故障诊断优化
本文作者:刘涛 文章目录 前言1.LVS/DR集群的问题2.华为云环境3.问题排查3.1 检查LVS/DR模式配置3.1.1 RS服务器3.1.2 DS服务器 3.2 继续分析抓包结果3.2.1 调整tcpdump抓包过滤条件3.2.2 client向集群VIP发包3.2.3 DS服务器arp消息 3.3 查看丢包3.3.1 监控DS和RS服…...
leetcode hot100除自身以外的数组的乘积
238. 除自身以外数组的乘积 已解答 中等 相关标签 相关企业 提示 给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在…...
SQL server学习09-数据库编程(上)
目录 一,了解T-SQL语言 1,常量(标量值) 2,变量 1)局部变量 2)全局变量 二,内置函数 1,字符串函数 2,数学函数 3,日期时间函数 4&#x…...
什么?Flutter 可能会被 SwiftUI/ArkUI 化?全新的 Flutter Roadmap
在刚刚过去的 FlutterInProduction 活动里,Flutter 官方除了介绍「历史进程」和「用户案例」之外,也着重提及了未来相关的 roadmap ,其中就有 3.27 里的 Swift Package Manager 、 Widget 实时预览 和 Dart 与 native 平台原生语言直接互操作…...
java全栈day19--Web后端实战(java操作数据库3)
一、MyBatis 1.1介绍 前提引入: controller(控制层)作用:接受请求,响应数据 service(业务层)作用:负责具体的逻辑处理 dao(持久层)作用:数据访问层 一般的访问流程:浏览器发起请求过来,先…...
【YashanDB知识库】Mybatis-Plus调用YashanDB怎么设置分页
本文内容来自YashanDB官网,原文内容请见 https://www.yashandb.com/newsinfo/7802958.html?templateId1718516 问题现象 Mybatis-Plus是Mybatis的增强工具,旨在简化开发者的CRUD操作,目前被广泛应用,Mybatis-Plus框架适配了多种…...
Ansible 批量管理华为 CE 交换机
注:本文为 “Ansible 管理华为 CE 交换机” 相关文章合辑。 使用 CloudEngine - Ansible 批量管理华为 CE 交换机 wsf535 IP 属地:贵州 2018.02.05 15:26:05 总体介绍 Ansible 是一个开源的自动化运维工具,AnsibleWorks 成立于 2012 年&a…...
基于自定义注解与 AOP 切面实现接口日志全面数据库存储
基于自定义注解与 AOP 切面实现接口日志全面数据库存储 一、引言 在当今复杂的软件系统开发与运维过程中,详细且精准地记录接口的各项信息对于系统性能监测、问题排查、安全审计以及业务分析都有着极为关键的意义。本文将深入讲解如何运用自定义注解与 AOP&#x…...
GraalVM完全指南:云原生时代下使用GraalVM将Spring Boot 3应用转换为高效Linux可执行文件
一、前言 在现代软件开发中,启动速度和资源利用率常常是衡量应用性能的关键指标。对于基于Spring Boot的应用来说,虽然它们易于开发和部署,但JVM的启动时间有时会成为一个瓶颈。本文介绍如何使用GraalVM将Spring Boot 3应用编译成原生Linux可执行文件,从而显著提高启动速度…...
单片机:实现驱动超声波(附带源码)
单片机实现驱动超声波模块 超声波模块(如HC-SR04)广泛应用于距离测量、避障系统、自动驾驶等嵌入式项目中。它能够通过发射超声波信号并接收反射波来计算物体的距离。本文将介绍如何使用单片机(如51系列单片机)驱动超声波模块&am…...
2025.01.15python商业数据分析top2
一、 导入项目 导入项目、准备项目数据 import pandas as pd# 文件路径为python文件位置下的相对路径dwxpd.read_excel("电蚊香套装市场近三年交易额.xlsx") fmfzpd.read_excel("防霉防蛀片市场近三年交易额.xlsx") msmcpd.read_excel("灭鼠杀虫剂市…...
信息系统项目管理-绩效考核
1.1.组织战略 组织的产品和服务战略的类型通常可以分为:技术密集型、()、目标动态型。 A市场导向型 B成本导向型 C人力密集型 D产品导向型 答案B 在组织的四项基本能力中,建立战略性奖励措施,根据员工对组织的贡献&am…...
【Linux】数据呈现
一、数据的输入与输出 1、标准文件描述符 Linux系统会将每个对象都当做文件来处理,包括输入和输出。它用文件描述符来标识每个文件对象。 文件描述符是一个非负整数,唯一会标识的是会话中打开的文件。每个进程一次最多可以打开9个文件描述符。bash sh…...
oracle 加字段和字段注释 sql
在 Oracle 数据库中,你可以使用 ALTER TABLE 语句来添加字段,并使用 COMMENT ON COLUMN 语句来添加字段注释。以下是一个示例: 假设你有一个名为 employees 的表,你想要添加一个名为 email 的字段,并为其添加注释。 …...
计算机网络压缩版
计算机网络到现在零零散散也算过了三遍,一些协议大概了解,但总是模模糊糊的印象,现在把自己的整体认识总结一下,(本来想去起名叫《看这一篇就够了》,但是发现网上好的文章太多了,还是看这篇吧&a…...
一文了解 gis 相关服务=》及前端地图服务相关总结
文章目录 概要OGC技术名词解释cesium 应用案例openlayers 中应用实例XYZ服务OSM服务WMS服务WMTS服务WFS服务 mapbox 应用实例矢量瓦片服务栅格瓦片服务WMS服务WFS服务 leaflet 中 地图服务实例加载OpenStreetMap瓦片图层加载自定义XYZ瓦片图层加载WMS服务图层加载WFS服务图层加…...
Brocade G610 配置
配置流程 zone创建–>cfg创建–>ip配置–>cfg启动并保存 查看端口信息 G610:admin> switchshow switchName: G610 switchType: 170.5 switchState: Online switchMode: Native switchRole: Principal switchDomain: 1 switchId: ff…...
DuetWebControl 开源项目常见问题解决方案
DuetWebControl 开源项目常见问题解决方案 DuetWebControl A completely new web interface for the Duet electronics [这里是图片001] 项目地址: https://gitcode.com/gh_mirrors/du/DuetWebControl 一、项目基础介绍 DuetWebControl 是一个为 RepRapFirmware 设计的完全响…...
亚信安全举办“判大势 悟思想 强实践”主题党日活动
为深入学习和贯彻党的二十届三中全会精神,近日,亚信安全举办了 “学习贯彻党的二十届三中全会精神——‘判大势 悟思想 强实践’党日活动”,并取得圆满成功。 本次活动特邀南京市委宣讲团成员、南京市委党校市情研究中心主任王辉龙教授出席。…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...
