如何修正我的质因数分解程序？

Question

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

输入：11 输出：11

输入：40 输出：2 2 2 5

输入：5427 输出：3 3 3 3 67

输入：435843 输出：3 3 79 613

输入：23456789 输出：none（似乎是一个无限循环，代码应该是 return 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; }。它根本没有用。

Answer 2

无论代码多么高效，对大数进行因式分解都需要一段时间 - 时间长到让人感觉电脑已经挂了。根据您的代码，即使是适度的大数字也需要很长时间。

要提高代码效率，您可以做的主要事情是注意对于数字的任何一对因数，其中一个不会超过数字的平方根。您可以使用这个事实来限制循环，以将 O(n) 的算法阶数减少到 O(log n)。

long sqrt = Math.sqrt(number);

for (long i = 2; i < sqrt; i++) {
    ...

您还可以做很多其他事情，但此更改将产生最大影响。

如果 number 在循环期间更改值（例如在您的第二个因式分解循环中），您当然需要重新计算最终值：

for (...)
    // if number changes
    sqrt = Math.sqrt(number);

如何修正我的质因数分解程序？

How to correct my prime factorization program?

java

primes