当前位置: 首页 > article >正文

*【每日一题 提高题】[蓝桥杯 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) {
    //标准输入 一个n
       Scanner 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;
    }
}

http://www.kler.cn/a/450513.html

相关文章:

  • c++ [spdlog 配置与使用]
  • AIDD - 探索语言模型在药物分子生成方面的应用
  • web-密码安全口令
  • 【Mysql】truncate 和 delete的区别
  • 一体式IO模块:打印机加工产线国产化降本增效的新利器
  • 知乎 PB 级别 TiDB 数据库集群管控实践
  • ssm-day05 springmvc
  • 完全二叉树的权值(蓝桥杯2019年试题G)
  • Jenkins介绍
  • Eureka服务注册源码
  • springboot480基于springboot高校就业招聘系统设计和实现(论文+源码)_kaic
  • 用Python开启人工智能之旅(四)深度学习的框架和使用方法
  • 【es6复习笔记】箭头函数(5)
  • Eureka学习笔记-客户端
  • 5G CPE 主控CPU(上位机) 数据转发性能评估--基于5G模组和NEO3开发板评估
  • Dubbo 3.x源码(28)—Dubbo服务发布导出源码(7)应用级服务接口元数据发布
  • Java 网络编程 ②-TCP Socket
  • Electron -- Electron应用主要核心(二)
  • ABAP开发-权限控制
  • Android 蓝牙开发-传输数据
  • AIDD - 探索语言模型在药物分子生成方面的应用
  • iptables交叉编译(Hisiav300平台)
  • [cisco 模拟器] ftp服务器配置
  • 一个简单封装的的nodejs缓存对象
  • 828考研资料汇总
  • C++ QT chip layout tool开发浅思