网站开发可以用gif吗新手怎么做网页
文章目录
- 题目描述与示例
- 题目描述
- 输入描述
- 输出描述
- 示例
- 输入
- 输出
- 说明
- 解题思路
- 暴力解
- 质数筛
- 代码
- Python
- Java
- C++
- 时空复杂度
- 华为OD算法/大厂面试高频题算法练习冲刺训练
题目描述与示例
题目描述
RSA加密算法在网络安全世界中无处不在,它利用了极大些数因数分解的闲难度,数据越大,安全系数越高,给定一个32
位整数,请对其进行因数分解,找出是哪两个素数的乘积。
输入描述
1`个正整数`num
0 < num <= 2147483647
输出描述
如果成功找到,以单个空格分割,从小到大输出两个素数。分解失败,请输出-1 -1
示例
输入
15
输出
3 5
说明
因数分解后,找到两个素数3
和5
,使得3*5=15
,按从小到大排列后,输出3 5
解题思路
经典的大数分解问题。
关于素数相关的内容,可以详看算法题中常用数学概念、公式、方法汇总 里的相关部分。
暴力解
比较容易想到的暴力解法包含以下步骤
- 从小到大枚举所有小于
sqrt(num)
的数a
- 判断
num
是否可以整除a
,若- 不可以,则直接跳过。遍历下一个
a
- 可以,则进行后续判断
- 不可以,则直接跳过。遍历下一个
- 判断
a
是否是素数,若- 不是,则直接跳过。遍历下一个
a
- 是,则进行后续判断
- 不是,则直接跳过。遍历下一个
- 判断
b = num // a
是否是素数,若- 不是,则直接跳过。遍历下一个
a
- 是,则
a b
为答案。
- 不是,则直接跳过。遍历下一个
上述过程慢的原因主要在于,计算a
或b
是否是素数的环节。
可以使用质数筛来优化上述过程。
质数筛
使用质数筛解决上述大数分解的过程如下
- 构建长度为
num+1
的质数筛数组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):# 构建埃氏筛,长度为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
了解更多