素数之积/RSA加密算法（C语言）
题目描述
RSA加密算法在网络安全世界中无处不在，它利用了极大整数因数分解的困难度，数据越大，安全系数越高，给定一个32位正整数，请对其进行因数分解，找出是哪两个素数的乘积。
输入描述
一个正整数num，0 < num <= 2147483647
输出描述
如果成功找到，以单个空格分割，从小到大输出两个素数，分解失败，请输出-1, -1
用例
| 输入 | 15 |
|---|---|
| 输出 | 3 5 |
| 输入 | 27 |
|---|---|
| 输出 | -1 -1 |
代码
#include <stdio.h>
#include <stdlib.h>
// 定义一个判断整数是否为素数的函数
int isPrime(int n) {
// 对于小于等于3的数，只有2和3是素数
if (n <= 3) {
return n > 1;
}
// 遍历从2到sqrt(n)，检查是否有能被n整除的数
for (int i = 2; i * i <= n; i++) {
// 如果找到一个能整除n的数i，则该数不是素数
if (n % i == 0) {
return 0;
}
}
// 若遍历结束后未找到能整除n的数，则n是素数
return 1;
}
int main() {
int num; // 定义变量num存储用户输入的32位正整数
scanf("%d", &num); // 读取用户输入的整数
// 判断num本身是否为素数，如果是素数则无法进行因数分解
if (isPrime(num)) {
printf("-1 -1\n"); // 输出分解失败标识
return 0; // 结束程序
}
// 遍历可能的因子，寻找合适的两个素数因子
for (int i = 2; i * i <= num; i++) {
// 如果当前数i能整除num
if (num % i == 0) {
int j = num / i; // 计算另一个因子j
// 检查i和j是否都是素数
if (isPrime(i) && isPrime(j)) {
// 如果两者均为素数，则输出分解结果（按升序排列）
printf("%d %d\n", i < j ? i : j, j > i ? j : i);
return 0; // 结束程序
}
}
}
// 如果循环结束仍未找到合适的素数因子，则输出分解失败标识
printf("-1 -1\n");
return 0; // 结束程序
}
优化
// 函数：检查一个数是否为素数
int isPrime(int num) {
if (num <= 3) {
return num > 1;
}
if (num % 6 != 1 && num % 6 != 5) {
return 0;
}
for (int i = 5; i <= sqrt(num); i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return 0;
}
}
return 1;
}
这段代码也是一个用于检查给定整数num是否为素数的函数。与之前提供的 isPrime 函数相比，它进行了以下优化：
-
首先，仍然保留了对小于等于3的数的特殊处理：只有2和3是素数。
-
然后，新增了一个条件判断，利用数学性质快速排除一部分非素数：
- 大多数合数（非素数）都可以表示为6k±1的形式，其中k是一个正整数。
- 因此，如果一个数
num不能被6整除且余数不是1或5，则该数一定不是素数，可以直接返回0。
-
对于可能的素数，循环从5开始，并以6为步长进行遍历。这是因为基于上述数学性质，我们只需要检查形如 6k ± 1 的数即可，而这些数位于序列 5, 7, 11, 13, 17, … 中，它们与6的关系恰好是以6为步长进行递增。
-
在循环体内，只需检查
num能否被i或者i + 2整除，若能则返回0，表示num不是素数。
通过以上优化，这个版本的 isPrime 函数在处理较大整数时可以减少不必要的计算量，提高了判断效率。
原文地址：https://blog.csdn.net/weixin_45912291/article/details/136237970
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！