高端营销网站,网页设计怎样做,保定手机网站建设,wordpress修改wpadmin文章目录 题目描述与示例题目描述输入描述输出描述示例输入输出说明 解题思路暴力解质数筛 代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
RSA加密算法在网络安全世界中无处不在#xff0c;它利用了极大些数因数分解的闲难… 文章目录 题目描述与示例题目描述输入描述输出描述示例输入输出说明 解题思路暴力解质数筛 代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
RSA加密算法在网络安全世界中无处不在它利用了极大些数因数分解的闲难度数据越大安全系数越高给定一个32位整数请对其进行因数分解找出是哪两个素数的乘积。
输入描述
1个正整数num
0 num 2147483647输出描述
如果成功找到以单个空格分割从小到大输出两个素数。分解失败请输出-1 -1
示例
输入
15输出
3 5说明
因数分解后找到两个素数3和5使得3*515按从小到大排列后输出3 5
解题思路
经典的大数分解问题。
关于素数相关的内容可以详看算法题中常用数学概念、公式、方法汇总 里的相关部分。
暴力解
比较容易想到的暴力解法包含以下步骤
从小到大枚举所有小于sqrt(num)的数a判断num是否可以整除a若 不可以则直接跳过。遍历下一个a可以则进行后续判断 判断a是否是素数若 不是则直接跳过。遍历下一个a是则进行后续判断 判断b num // a是否是素数若 不是则直接跳过。遍历下一个a是则a b为答案。
上述过程慢的原因主要在于计算a或b是否是素数的环节。
可以使用质数筛来优化上述过程。
质数筛
使用质数筛解决上述大数分解的过程如下
构建长度为num1的质数筛数组sieve。sieve[i]是True表示i是质数sieve[i]是False表示i是合数。枚举质数筛中每一个质数a即sieve[a] True的下标。判断num是否可以整除a若 不可以则直接跳过。遍历下一个a可以则进行后续判断 判断b num // a是否是素数若 不是则直接跳过。遍历下一个a是则a b为答案。
代码
Python
# 题目【模拟】2023C-素数之积
# 分值100
# 作者许老师-闭着眼睛学数理化
# 算法数学
# 代码看不懂的地方请直接在群上提问from math import floor, sqrt# 使用埃氏筛计算数组
def sieve_of_eratosthenes(n):# 构建埃氏筛长度为n1初始化均为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 ListInteger 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;}}}ListInteger 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();ListInteger primes sieveOfEratosthenes(num);SetInteger 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_setstd::vectorint sieve_of_eratosthenes(int n) {std::vectorbool 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::vectorint 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::vectorint primes sieve_of_eratosthenes(num);std::unordered_setint 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动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
