求两个质数乘积中的较大质数 - Java 代码实现 - 常规

求两个质数乘积中的较大质数 - Java 代码实现

给定一个正整数 n，已知它是两个不同质数的乘积，本篇文章将介绍如何使用 Java 代码找出较大的那个质数。

算法思路

判断质数: 首先，我们需要判断一个数是否为质数。质数是只能被 1 和自身整除的数，所以我们可以从 2 开始，逐个尝试除以小于该数的所有数，如果都不能整除，则该数是质数。
寻找较大质数: 接下来，我们需要找出两个质数的乘积为给定的数 n。我们可以从 n 的平方根开始，逐个递减尝试，找到第一个能整除 n 的质数。这个质数即为较大的那个质数。

代码实现

import java.util.Scanner;

public class Main {
    // 判断一个数是否为质数
    public static boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        for (int i = (int)Math.sqrt(n); i > 1; i--) {
            if (n % i == 0 && isPrime(i)) {
                System.out.println(i);
                break;
            }
        }
    }
}

代码解释

isPrime 方法: 该方法用于判断一个数是否为质数。如果输入的数小于 2，则直接返回 false。否则，从 2 开始，循环遍历小于等于该数平方根的所有数，如果能整除该数，则返回 false，否则继续循环。如果循环结束后都没有返回 false，则说明该数是质数，返回 true。
main 方法: 该方法用于读取输入的正整数 n，并进行计算。首先，我们从 n 的平方根开始，逐个递减尝试，找到第一个能整除 n 且为质数的数，输出该数，即为较大的那个质数。

优化建议

优化 isPrime 方法: 由于我们只关心 n 的平方根及以下的质数，可以提前计算出小于等于 n 的平方根的所有质数，并存储在数组或集合中，在 isPrime 方法中直接判断是否在该集合中，可以提高效率。
优化循环: 可以使用更有效的算法，例如试除法或 Miller-Rabin 检验，来判断质数，进一步提高效率。

通过以上代码和解释，你应该已经了解了如何使用 Java 代码求解两个质数乘积中的较大质数。希望这篇文章对你有所帮助！