【算法题】素数之积

339次阅读
没有评论

共计 1036 个字符,预计需要花费 3 分钟才能阅读完成。

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

输入:一个正整数num(0 < num <= 2147483647)
输出:如果成功找到,以单个空格分割,从小到大输出两个素数,分解失败,请输出-1 -1

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

输入 27
输出 -1 -1
说明 通过因数分解,找不到任何素数,使得他们的乘积为27,输出-1 -1

  1. 如果一个数字不是素数 那它除了1和他本身一定还有别的约数
  2. 如果一个数的约数在其开平方的右边 则必然会存在一个约数在其开平方的左边
  3. 判断一个数是否为质数 只需要观察在其2 到 开平方数中间是否含有约数即可
    比如说 判断16是否为质数 我们去找16的约数时 判断它的范围 只需要找到
    16的开平方数就可以了 而不必一直找到<16 或者<= 16/2
import java.util.Scanner;

/**
 * @since 2022-04-11
 */
public class ProductOfPrime {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int a = -1;
        int b = -1;
        // 计算输入数字的平方根,原因如上
        double sqrt = Math.sqrt(num);
        for (int i = 2; i <= sqrt; i++) {
            // 判断是否为素数
            if (!isPrime(i)) {
                continue;
            }
            // 判断能否整除
            if (num % i != 0) {
                continue;
            }
            // 判断另一个乘数是否为素数
            if (!isPrime(num / i)) {
                continue;
            }
            // 结果赋值
            a = i;
            b = num / i;
        }

        System.out.println(a + " " + b);
    }

    /**
     * 判断是否是素数
     *
     * @param arg 入参
     * @return bool
     */
    public static boolean isPrime(int arg) {
        if (arg <= 1) {
            return false;
        }
        // 计算输入数字的平方根,原因如上
        double sqrt = Math.sqrt(arg);
        for (int j = 2; j <= sqrt; j++) {
            if (arg % j == 0) {
                return false;
            }
        }
        return true;
    }

}
正文完
 0
裴先生
版权声明:本站原创文章,由 裴先生 2022-04-12发表,共计1036字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
本站勉强运行: