使用 Java 进行质因数分解并找到上界

Question

这就是我想要做的。我在下面列出了我的代码供您参考。预先感谢您提供的任何帮助。

目标：找到数字 n 的质因数分解。然后将素数连接成一个数字 x。然后取那个数字 x，然后除以 n。如果 x%n = 0，打印 True。如果 x%n != 0，打印 false。（即如果 n = 100，质因数为 2,2,5,5。变成 2255，然后取 2255/100。2255%100 != 0，打印 False。）

我现在可以正确打印出一些数字的质因数，但是当我尝试使用另一个质数时，程序将退出。另外，如果我使用像 123 这样的数字，它只会打印出 3，而不是 3 和 41。你有什么建议吗？

如果可能的话，理想情况下我想运行对于数字 j= 2 通过我设置的任何上限，调用上限 U，如果 j = 2 到 U 的任何值产生结果这是真的（从上面）然后我想打印那个 j 值。

import acm.program.*;
import acm.util.*;
import java.util.Scanner;
import java.util.Arrays.*;
// -------------------------------------------------------------------------

public class FactorsLoop extends ConsoleProgram
{
//~ Instance/static variables .............................................
private RandomGenerator rgen = RandomGenerator.getInstance();
//~ Constructor ...........................................................
// ----------------------------------------------------------
/**
 * Creates a new ForLoops object.
 */
public void run()
{
    // 


    int n1 = 10000;
    int n2 =(n1);

    double U = 10000;
    StringBuilder factors = new StringBuilder();
    for (int j = 2; j < U; j++) {

        for (int i = 2; i*i <= n1; i++) {
            // if i is a factor of N, repeatedly divide it out
            while (n1% i == 0) {

                n1 = n1 / i;


                factors.append(Integer.toString(i));

            }

        }

    }

    double newNumber = Integer.parseInt(factors.toString());

    double x = (newNumber / n2);

    print(x);

    if ( newNumber % n2 == 0 ){
        println(n2);    
    }
}

}

Answer 1

您的代码正确地将所有这些素数添加到它除掉的 factors 中。但是，它还应该在循环后添加 n1，如果它恰好是 != 1（这将恰好发生在最大因子的幂为 1 时）。

原因是您的代码进行了优化，当当前因子超过 sqrt(n1) 时退出内部循环（for 循环 header 中的条件 i*i <= n1）。这是一个有效的优化，但像许多优化一样，它使逻辑更加复杂并且 error-prone...

注意：迭代j的外层循环似乎没有任何意义；只会导致重复附加小因素。使内部循环进入工作状态，将其分解为一个单独的函数（双关语），然后使用它来实现您的范围测试，该测试寻找满足某些标准的第一个结果。

例如，returns 串联因子的函数可能如下所示：

public string concatenated_factors (int n)
{
    StringBuilder result = new StringBuilder();

    for (int i = 2; i * i <= n; ++i)
        for ( ; n % i == 0; n /= i)
            result.append(Integer.toString(i));

    if (n != 1)
        result.append(Integer.toString(n));

    return result.toString();
}

注意：我不熟悉Java，所以这里有些细节可能有点模糊。

使用 Java 进行质因数分解并找到上界

Prime Factorization With Java and Finding an Upper Bound

java

primes

prime-factoring