问在Java中返回素因子字符串

EN

由于n小于固定数( 109 )，所以只需使用包含所有素数<= 109的表，而不是动态生成它们。或者，至少先用橡皮筋或阿特金筛来生成引物。硬编码的表会更好，但是使用一个用于动态生成表的筛子将大大加快速度。您实现的isPrime()函数是性能杀手。

函数isPrime()在primefactors中调用次数太多。例如，i == 2和n中有许多除数2。顶级呼叫(isPrime(i))很好。但是，在循环while (n % i == 0)中，您可以在每个除法isPrime(n)之后检查n /= 2;。因此，如果初始n为100，则为50调用函数isPrime()，在下一个循环中调用25函数。这没有任何意义。我认为这是这里最大的问题，因为即使isPrime在线性时间工作，在内部循环中多次调用它也太过了。

可以在两种情况下退出i的循环:除法后的n是相等的1，如果i大于sqrt(n)，则n肯定是素数。

public String primefactors(int n) {
    String factors = "";
    int max_divisor = sqrt(n);
    for (int i = 2; i <= max_divisor; i++) {
        if (isPrime(i)) {
            while (n % i == 0) {
                n /= i;
                if (n == 1)
                    factors = factors + Integer.valueOf(i).toString();
                else
                    factors = factors + Integer.valueOf(i).toString() + "*";
            }
            max_divisor = sqrt(n);
        }
    }
    // check for the last prime divisor
    if (n != 1)
        factors = factors + Integer.valueOf(n).toString();

    return factors;
}

即使在改进之后(以及sqrt(n)作为isPrime()中的最大限制)，您的算法也将具有线性复杂度O(n)，因为i最多有sqrt(n)循环，而isPrime中素数的最大探测数也是sqrt(n)。

是的，通过为isPrime()选择更好的算法可以做得更好。即使不允许使用硬编码的素数表，也可以在运行时生成这样的查找表(如果有足够的内存)。因此，可以使用自动生成的素数列表(按升序排列)来探测给定的编号，直到sqrt(n)。如果i大于sqrt(n)，则意味着找到下一个素数，并将其追加到查找表中，isPrime()应该返回true。

示例

假设isPrime被调用为113。此时，查找表有一个以前的素数列表：2,3,5,7,11,13...。因此，我们尝试将113从该列表中的项除以sqrt(113) (while (i <= 10))。尝试2,3,5,7后，列表中的下一项11太大，因此113被追加到素数列表中，函数返回true。

在最坏的情况下，其他算法可以提供更好的性能。例如，Eratosthenes的筛子或Atkin的筛子可以有效地预先计算到给定n的素数列表，具有最佳的O(n)复杂度，以获得最佳的实现。在这里，您需要找到sqrt(n)的所有素数，所以需要O(sqrt(n))来生成这样的列表。一旦生成这样的列表，您就需要尝试将输入除以数字，这是最多接受sqrt(n)探测的列表。因此，算法的复杂度是O(sqrt(n))。但是，假设您的输入是1024，即2到10的威力。在这种情况下，第一种算法会更好，因为它不会变成比2更大的素数。

你真的需要函数isPrime()吗？

用灵活的思维，如果我们仔细观察，似乎你不必在某个范围内寻找所有的素数。您只需要找到一个给定整数的所有素数除数。但是，如果我们尝试将n除以，则所有整数都在sqrt(n)范围内，这也是一个很好的解决方案。即使这个整数不是素数，由于条件n % i == 0，它也会被跳过，因为所有低于被测试整数的素数都已经从n中删除了，所以简单的模块化除法在这里和isPrime()一样。具有O(sqrt(n))复杂性的完整解决方案：

public String primefactors(int n) {
    String factors = "";
    int max_divisor = sqrt(n);
    for (int i = 2; i <= max_divisor; i++) {
        while (n % i == 0) {
            n /= i;
            max_divisor = sqrt(n);
            if (n == 1)
                factors = factors + Integer.valueOf(i).toString();
            else
                factors = factors + Integer.valueOf(i).toString() + "*";
        }
    }
    // check for the last prime divisor
    if (n != 1)
        factors = factors + Integer.valueOf(n).toString();

    return factors;
}

为了避免内部循环中的if (n == 1)检查，还可以拆分函数，但是它不会改变算法的复杂性。