java - 如何修正我的素因数分解程序？

Question

这是我的程序，用于输出给定数字的素因数分解。我仍然只是 java 的初学者，所以我知道这不是最有效的代码。当我输入相对较大的数字时，就会出现问题。

输入:11 输出:11

输入:40 输出:2 2 2 5

输入:5427 输出:3 3 3 3 67

输入:435843 输出:3 3 79 613

输入:23456789 输出:无(似乎存在无限循环，代码应返回 23456789，因为它本身就是一个素数)

什么可能导致此问题？

import java.util.Scanner;

public class PrimeFactorization {
    public static boolean isPrime(long n) {
        boolean boo = false;
        long counter = 0;
        if (n == 1) {
            boo = false;
        } else if (n == 2) {
            boo = true;
        } else {
            for (long i = 2; i < n; i++) {
                if (n % i == 0) {
                    counter++;
                }
            }
            if (counter == 0) {
                boo = true;
            }
        }
        return boo;
    }

    public static void primeFactorization(long num) {
        for (long j = 1; j <= num; j++) {
            if (isPrime(j)) {
                if (num % j == 0) {
                    while (num % j == 0) {
                        System.out.printf(j + " ");
                        num = num / j;
                    }
                }
            }
            if (num == 1) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter any number:");
        long num = scanner.nextLong();
        System.out.print("Prime factorization of your number is: ");
        primeFactorization(num);
        scanner.close();
    }
}

Answer 1

没有实际的错误 - 你只是以一种非常低效的方式做事。基本上，您在除法之前检查 1 到 23456789 之间的每个数字是否为素数。

进行此检查绝对没有意义。当您从 1 递增到 23456789 时，每次发现一个因子时，您都知道它必须是质数，因为您已经除掉了所有较小的因子。因此，如果您执行以下所有操作，这仍然可以正常工作，而且速度更快。

• 完全删除 isPrime 方法。
• 删除 if (isPrime(j)) { 行以及匹配的 }
• 更改循环，使 j 从 2 开始，如 for(long j = 2 ; j <= num ; j++) {
• 从循环末尾删除 if (num == 1) { break; }。它根本没有任何作用。