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

【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【数学】2023C-素数之积【欧弟算法】全网注释最详细分类最全的华为OD真题题解

文章目录

  • 题目描述与示例
    • 题目描述
    • 输入描述
    • 输出描述
    • 示例
      • 输入
      • 输出
      • 说明
  • 解题思路
    • 暴力解
    • 质数筛
  • 代码
    • Python
    • Java
    • C++
    • 时空复杂度
  • 华为OD算法/大厂面试高频题算法练习冲刺训练

题目描述与示例

题目描述

RSA加密算法在网络安全世界中无处不在,它利用了极大些数因数分解的闲难度,数据越大,安全系数越高,给定一个32位整数,请对其进行因数分解,找出是哪两个素数的乘积。

输入描述

1`个正整数`num
0 < num <= 2147483647

输出描述

如果成功找到,以单个空格分割,从小到大输出两个素数。分解失败,请输出-1 -1

示例

输入

15

输出

3 5

说明

因数分解后,找到两个素数35,使得3*5=15,按从小到大排列后,输出3 5

解题思路

经典的大数分解问题。

关于素数相关的内容,可以详看算法题中常用数学概念、公式、方法汇总 里的相关部分。

暴力解

比较容易想到的暴力解法包含以下步骤

  1. 从小到大枚举所有小于sqrt(num)的数a
  2. 判断num是否可以整除a,若
    1. 不可以,则直接跳过。遍历下一个a
    2. 可以,则进行后续判断
  3. 判断a是否是素数,若
    1. 不是,则直接跳过。遍历下一个a
    2. 是,则进行后续判断
  4. 判断b = num // a是否是素数,若
    1. 不是,则直接跳过。遍历下一个a
    2. 是,则a b为答案。

上述过程慢的原因主要在于,计算ab是否是素数的环节。

可以使用质数筛来优化上述过程。

质数筛

使用质数筛解决上述大数分解的过程如下

  1. 构建长度为num+1的质数筛数组sievesieve[i]True表示i是质数,sieve[i]False表示i是合数。
  2. 枚举质数筛中每一个质数a,即sieve[a] = True的下标。
  3. 判断num是否可以整除a,若
    1. 不可以,则直接跳过。遍历下一个a
    2. 可以,则进行后续判断
  4. 判断b = num // a是否是素数,若
    1. 不是,则直接跳过。遍历下一个a
    2. 是,则a b为答案。

代码

Python

# 题目:【模拟】2023C-素数之积
# 分值:100
# 作者:许老师-闭着眼睛学数理化
# 算法:数学
# 代码看不懂的地方,请直接在群上提问from math import floor, sqrt# 使用埃氏筛计算数组
def sieve_of_eratosthenes(n):# 构建埃氏筛,长度为n+1,初始化均为True,表示默认为质数sieve = [True] * (n + 1)# 0和1不是质数sieve[0], sieve[1] = False, False# 枚举从2到floor(sqrt(x))的每一个数xfor x in range(2, floor(sqrt(n)) + 1):# 如果x是一个质数,则说明其m倍(m >= 2)的所有正整数是合数if sieve[x] == True:# 将mx标记为Falsefor i in range(2 * x, n + 1, x):sieve[i] = False# 退出循环后,sieve中所有为True的元素下标为质数primes = [i for i in range(n + 1) if sieve[i]]return primesnum = int(input())
# 计算所有小于num的素数
primes = sieve_of_eratosthenes(num)
primes_set = set(primes)# 初始化一个标记,表示是否找到一组素数
isFind = False
# 遍历所有小于num的素数a
for a in primes:# 如果num可以整除aif num % a == 0:# 则计算b是否也是素数b = num // a# 如果是,则输出(a, b)# 同时标记isFind为True,表示计算得到一组答案# 同时退出循环if b in primes_set:print(a, b)isFind = Truebreak# 如果退出循环后,isFind仍为False,则输出(-1, -1)
if isFind == False:print(-1, -1)

Java

import java.util.*;public class Main {public static List<Integer> sieveOfEratosthenes(int n) {boolean[] sieve = new boolean[n + 1];Arrays.fill(sieve, true);sieve[0] = sieve[1] = false;for (int x = 2; x * x <= n; ++x) {if (sieve[x]) {for (int i = x * x; i <= n; i += x) {sieve[i] = false;}}}List<Integer> primes = new ArrayList<>();for (int i = 2; i <= n; ++i) {if (sieve[i]) {primes.add(i);}}return primes;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();List<Integer> primes = sieveOfEratosthenes(num);Set<Integer> primesSet = new HashSet<>(primes);boolean isFind = false;for (int a : primes) {if (num % a == 0) {int b = num / a;if (primesSet.contains(b)) {System.out.println(a + " " + b);isFind = true;break;}}}if (!isFind) {System.out.println("-1 -1");}}
}

C++

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_set>std::vector<int> sieve_of_eratosthenes(int n) {std::vector<bool> sieve(n + 1, true);sieve[0] = sieve[1] = false;for (int x = 2; x * x <= n; ++x) {if (sieve[x]) {for (int i = x * x; i <= n; i += x) {sieve[i] = false;}}}std::vector<int> primes;for (int i = 2; i <= n; ++i) {if (sieve[i]) {primes.push_back(i);}}return primes;
}int main() {int num;std::cin >> num;std::vector<int> primes = sieve_of_eratosthenes(num);std::unordered_set<int> primes_set(primes.begin(), primes.end());bool isFind = false;for (int a : primes) {if (num % a == 0) {int b = num / a;if (primes_set.find(b) != primes_set.end()) {std::cout << a << " " << b << std::endl;isFind = true;break;}}}if (!isFind) {std::cout << -1 << " " << -1 << std::endl;}return 0;
}

时空复杂度

时间复杂度:O(Nlog(NlogN))。构建质数筛所需要的时间

空间复杂度:O(1)。除了输入的序列,仅需若干常数变量维护遍历过程。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

相关文章:

【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【数学】2023C-素数之积【欧弟算法】全网注释最详细分类最全的华为OD真题题解

文章目录 题目描述与示例题目描述输入描述输出描述示例输入输出说明 解题思路暴力解质数筛 代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例 题目描述 RSA加密算法在网络安全世界中无处不在&#xff0c;它利用了极大些数因数分解的闲难…...

uniapp路由

1、路由登记 uni-app页面路由为框架统一管理&#xff0c;开发者需要在pages.json里配置每个路由页面的路径及页面样式。 类似小程序在 app.json 中配置页面路由一样。 所以 uni-app 的路由用法与 Vue Router 不同&#xff0c;如仍希望采用 Vue Router 方式管理路由&#xff0c;…...

湖南大学-数据库系统-2023期末考试【原题】

前言 早上11&#xff1a;00考完的考试&#xff0c;下午回来打了三把LOL之后&#xff0c;凭着回忆把题目重现出来了。 在复习的时候刷了15&#xff0c;16&#xff0c;17&#xff0c;18&#xff0c;19&#xff0c;21六年的卷子&#xff0c;感觉题目都差不多&#xff0c;但是难度…...

【Java EE初阶九】多线程案例(线程池)

一、线程池的引入 引入池---->主要是为了提高效率&#xff1b; 最开始&#xff0c;进程可以解决并发编程的问题&#xff0c;但是代价有点大了&#xff0c;于是引入了 “轻量级进程” ---->线程 线程也能解决并发编程的问题&#xff0c;而且线程的开销比进程要小的多&…...

理解 Node.js 中的事件循环

你已经使用 Node.js 一段时间了&#xff0c;构建了一些应用程序&#xff0c;尝试了不同的模块&#xff0c;甚至对异步编程感到很舒适。但是有些事情一直在困扰着你——事件循环&#xff08;Event Loop&#xff09;。 如果你像我一样&#xff0c;花费了无数个小时阅读文档和观看…...

Mac 软件出现「意外退出」及「打不开」解决方法

Mac 软件出现「意外退出」及「打不开」解决方法 软件出现意外退出及软件损坏的情况&#xff0c;这是因为苹果删除了TNT的证书&#xff0c;所以大部分TNT破解的Mac软件会出现无法打开&#xff0c;提示意外退出。 终端需先安装Xcode或Apple命令行工具 如未装Xcode可以使用下列命…...

随机森林 3(代码)

通过随机森林 1和随机森林 2 的介绍&#xff0c;相信大家对理论已经了解的很透彻&#xff0c;接下来带大家敲一下代码&#xff0c;不懂得可以加我入群讨论。 第一份代码是比较原始的代码&#xff0c;第二份代码是第一段代码中引用的primitive_plot&#xff0c;第三份代码是使用…...

勒索事件急剧增长,亚信安全发布《勒索家族和勒索事件监控报告》

近期(12.15-12.21)态势快速感知 近期全球共发生了247起攻击和勒索事件&#xff0c;勒索事件数量急剧增长。 近期需要重点关注的除了仍然流行的勒索家族lockbit3以外&#xff0c;还有本周top1勒索组织toufan。toufan是一个新兴勒索组织&#xff0c;本周共发起了108起勒索攻击&a…...

LeetCode1523. Count Odd Numbers in an Interval Range

文章目录 一、题目二、题解 一、题目 Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive). Example 1: Input: low 3, high 7 Output: 3 Explanation: The odd numbers between 3 and 7 are [3,5,7]. Exam…...

E中国铜金属行业需求前景及未来发展机遇分析报告2024-2030年

E中国铜金属行业需求前景及未来发展机遇分析报告2024-2030年 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 《报告编号》: BG471816 《出…...

python SVM 保存和加载模型参数

在 Python 中&#xff0c;你可以使用 scikit-learn 库中的 joblib 或 pickle 模块来保存和加载 SVM 模型的参数。以下是一个简单的示例代码&#xff0c;演示了如何使用 joblib 模块保存和加载 SVM 模型的参数&#xff1a; 保存模型参数&#xff1a; from sklearn import svm …...

JAVA进化史: JDK12特性及说明

JDK 12于2019年3月发布。这个版本相对于之前的版本来说规模较小&#xff0c;主要集中在一些改进和实验性的特性上。以下是JDK 12的一些主要特性&#xff1a; 引入了实验性的Shenandoah垃圾收集器 JDK 12引入了实验性的Shenandoah垃圾收集器&#xff0c;旨在实现极低的暂停时间…...

Databend 的算力可扩展性

作者&#xff1a;尚卓燃&#xff08;PsiACE&#xff09; 澳门科技大学在读硕士&#xff0c;Databend 研发工程师实习生 Apache OpenDAL(Incubating) Committer PsiACE (Chojan Shang) GitHub 对于大规模分布式数据处理系统&#xff0c;为了更好应对数据、流量、和复杂性的增长…...

「解析」Windows 如何优雅使用 Terminal

所谓工欲善其事必先利其器&#xff0c;对于开发人员 Linux可能是首选&#xff0c;但是在家学习的时候&#xff0c;我还是更喜欢使用 Windows系统&#xff0c;首先是稳定&#xff0c;其次是习惯了。当然了&#xff0c;我还有一台专门安装 Linux系统的小主机用于学习Linux使用&am…...

Linux第18步_安装“Ubuntu系统下的C语言编译器GCC”

Ubuntu系统没有提供C/C的编译环境&#xff0c;因此还需要手动安装build-essential软件包&#xff0c;它包含了 GNU 编辑器&#xff0c;GNU 调试器&#xff0c;和其他编译软件所必需的开发库和工具。本节用于重点介绍安装“Ubuntu系统下的C语言编译器&#xff27;&#xff23;&a…...

【Linux】Linux 基础命令 crontab命令

1.crontab命令 crond 是linux下用来周期性的执行某种任务或等待处理某些事件的一个守护进程,与windows下的计划任务类似,当安装完成操作系统后,默认会安装此服务 工具,并且会自动启动crond进程,crond进程每分钟会定期检查是否有要执行的任务,如果有要执行的任务,则自动…...

14:00面试,14:08就出来了,问的问题过于变态了。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到10月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40…...

Ubuntu envs setting

1. change the chmod of folders sudo chown -R $USER:$USER /home/anaconda3 2. torch.cuda.is_available()返回false change conda installation to pip. zai qi ta huan jing pei zhi dou mei wen ti de qing kuang xia , zai shi shi zhe ge fang fa. # CUDA 11.7 con…...

Windows 下用 C++ 调用 Python

文章目录 Part.I IntroductionChap.I InformationChap.II 预备知识 Part.II 语法Chap.I PyRun_SimpleStringChap.II C / Python 变量之间的相互转换 Part.III 实例Chap.I 文件内容Chap.II 基于 Visual Studio IDEChap.III 基于 cmakeChap.IV 运行结果 Part.IV 可能出现的问题Ch…...

九州金榜|家庭教育一招孩子不在任性

有一次和朋友一块聚餐&#xff0c;邻座是一位妈妈、和她大概七八岁的儿子&#xff0c;小男孩长得很帅气&#xff0c;没有像同龄人那样调皮捣乱&#xff0c;而是和妈妈很温馨的就餐。 看的出来一家人的素质很高&#xff0c;就餐过程中桌面保持的很整洁&#xff0c;交流声音也不…...

爬虫案列 --抖音视频批量爬取

""" 项目名称: 唯品会商品数据爬取 项目描述: 通过requests框架获取网页数据 项目环境: pycharm && python3.8 作者所属: 几许1. 对主页抓包 , 鼠标移动到视频位置视频自动播放获得视频数据包 2. 对视频数据包地址进行解析 , 复制链接 , 进行检索 3. 获…...

【React系列】React中的CSS

本文来自#React系列教程&#xff1a;https://mp.weixin.qq.com/mp/appmsgalbum?__bizMzg5MDAzNzkwNA&actiongetalbum&album_id1566025152667107329) 一. React中的css方案 1.1. react 中的 css 事实上&#xff0c;css 一直是 React 的痛点&#xff0c;也是被很多开发…...

基于Kettle开发的web版数据集成开源工具(data-integration)-应用篇

目录 &#x1f4da;第一章 基本流程梳理&#x1f4d7;页面基本操作&#x1f4d7;对应后台服务流程 &#x1f4da;第二章 二开思路&#x1f4d7;前端&#x1f4d7;后端 &#x1f53c;上一集&#xff1a;基于Kettle开发的web版数据集成开源工具(data-integration)-介绍篇 *️⃣主…...

51单片机三种编译模式的相互关系

51单片机三种编译模式的相互关系 编译模式默认存储类型RAM使用规模变量使用特点SAMLLdata128B片内RAM使用规模CPU访问数据速度快&#xff0c;但存储容量较小COMPACTpdata258B片外分页RAM速度和容量介于上下两者之间LARGExdata64KB片外RAMCPU访问数据的速度较慢&#xff0c;但存…...

java 千帆大模型 流式返回

聊天有两个接口,第一个是获取token, 第二个是聊天接口,具体参照官方文档 下面是流式调用聊天接口,单次的,不含上下文 Value("${qianfan.apiKey}")private String apiKey;Value("${qianfan.secretKey}")private String secretKey;Value("${qianfan.to…...

全新互联网洗衣洗鞋小程序平台新模式

互联网洗衣洗鞋新模式&#xff0c; 全新软件升级 对接各大平台 扩大营销渠道&#xff0c;增加效益&#xff01;...

js 对于一些脚本中对于url的一些参数获取

js 对于一些脚本中对于url的一些参数获取 获取当前浏览器的链接上的参数(不使用vue / react 等框架&#xff09;仅用在一些脚本上的使用 获取当前浏览器的链接上的参数(不使用vue / react 等框架&#xff09;仅用在一些脚本上的使用 const query {} const params new URLSear…...

IEDA中tomcat日志乱码解决

文章目录 乱码样式原因解决方案参考 乱码样式 原因 乱码原因是编码格式的问题&#xff0c;编码格式不统一&#xff0c;导致显示乱码。 解决方案 统一编码格式。 打开tomcat的配置文件&#xff0c;conf/logging.properties,进行如下修改 进入idea的安装文件中&#xff0c;b…...

计算机网络实验(六):三层交换机实现VLAN间路由

一、实验名称:三层交换机实现VLAN间路由 二、实验原理 2.1. VLAN基本配置 在交换网络中,为了实现对物理网络的逻辑划分,引入了VLAN(虚拟局域网)的概念。VLAN通过将不同的设备划分到不同的虚拟网络中,实现了逻辑隔离。基本配置包括在交换机上创建VLAN、将端口划分到相应…...

Flutter中showModalBottomSheet的属性介绍和使用

在Flutter中&#xff0c;showModalBottomSheet是一个常用的工具&#xff0c;用于在屏幕底部显示模态底部面板。了解其属性将帮助您更好地定制和控制底部模态框的外观和行为。 showModalBottomSheet的常用属性 1. context: 类型: BuildContext描述: 表示当前构建上下文&#…...

WordPress进/兰州网站seo诊断

DevExpress广泛应用于ECM企业内容管理、 成本管控、进程监督、生产调度&#xff0c;在企业/政务信息化管理中占据一席重要之地。通过DevExpress WPF Controls&#xff0c;您能创建有着强大互动功能的XAML基础应用程序&#xff0c;这些应用程序专注于当代客户的需求和构建未来新…...

wordpress跳转到手机版/国外搜索引擎排名百鸣

1.第一种(自己想的) money count 将money分成count份 在自己的count份里面随机选择 /** * 随机红包(最后拆红包的在数组里面再随机选择)* param money* param count* return* see[类、类#方法、类#成员]*/public static double[] randomMoney(double money, int count){/…...

正规代加工项目招商/seo关键词排名点击工具

区块如何连接成区块链之前的文章里又说到区块链&#xff0c;想要知道区块链上的信息首先需要了解一下什么是区块链&#xff0c;区块链其实是一串使用密码学算法产生的区块连接而成。每一个区块上写满了交易记录&#xff0c;区块按顺序相连形成链状结构&#xff0c;就像世界上的…...

精美网站制作/企业文化案例

最近一直在忙着和数据库有关的一些工作&#xff0c;这几天在写存储过程的时候&#xff0c;一些mysql的语句突然感觉有些不太明白&#xff0c;就是group by &#xff0c; order by &#xff0c;where &#xff0c; having这些语句&#xff0c;这次通过一个实例来总结…...

朔州网站建设价格/小程序开发软件

本文转载自&#xff1a;http://www.blogjava.net/BlueDavy/archive/2009/04/28/267970.html&#xff0c; 转载请注明 在这篇blog中放置了我收集的一些网站架构相关的PPT和文章&#xff0c;提供给大家下载&#xff0c;如果大家有相关的好的PPT、文章的话&#xff0c;也欢迎推…...

做网站需要硬件设施/免费个人网站建站申请

写在前面&#xff1a;jQuery是一个简化js的框架&#xff0c;可以方便的操作DOM&#xff0c;操作类&#xff0c;注册事件&#xff0c;发送ajax等 入口函数 $(document).ready(function( )) $(function(){ }) 操作DOM $(#id) $(.class) $(div) $(div,p,li) $(div.redClass)…...