java - 需要帮助查找分解代码中的错误

Question

我正在编写一个程序，将一个数字分解为质因数。该程序的工作原理如下:

1)输入您想要分解的数字(我将称为“inputNumber”)

2) 测试是否可以将 inputNumber 除以 2、3、5 和 7(前 4 个质数)。如果你能除以其中任何一个，那么就尽可能多次除以(即 12 可以除以 2 两次，之后余数为 3) 注意每次我除以一个数字时，我都会将该数字存储在数组列表中，并保留余数以供进一步测试

3)从 while 循环中的 i=11(下一个素数)开始，我执行以下操作:

while (i < remainder+1) { 
divides by i? yes: store i, 
repeat until you cant divide by i. i=i+2, 
divides by i? yes: store i, repeat until you can't divide by i.
 i=i+4, same as before... i=i+2... 
and finally stop the loop at i=i+2 
} 

这样，每次成功的 while 循环迭代都会将余数除以最后的数字 1,3,7,9。我们不需要测试偶数，因为我们已经除以 2，也不需要测试以 5 结尾的数字，因为我们已经除以 5。最后，我们

这是一种非常巧妙的算法，因为它比通过一个接一个地测试数字来分解数字要快得多，事实上，您只需要测试所有数字的 40%。

我的问题是:当我尝试分解 84738329279(一个随机选择的数字)时，它忽略了将最后一个质因数放入列表中，我不太明白这一点。唯一显示的因子是 41、61 和 61。有人可以帮助我找出我做错了什么吗？这是我的代码:

import java.util.Scanner;
import java.math.BigInteger;

public class Test {

public static void main(String[] args) {
                    // create a scanner object for inputs
            Scanner in = new Scanner(System.in);

            // prompt user for number to factor
            System.out.print("enter a number to factor: ");
            String digits = in.next();
            BigInteger BigDigits = new BigInteger(digits);

            BigInteger[] results = factor.factorThis(BigDigits);


            System.out.print("Factors are ");
            for (int i=0; i<results.length;i++){
            System.out.print(results[i] + " ");
            }
            System.out.println("");
        }
}

import java.util.ArrayList;
import java.math.BigInteger;


public class factor {

// Returns the prime factors of the BigInteger number
public static BigInteger[] factorThis(BigInteger number) {

    BigInteger i = new BigInteger("11");
    ArrayList<BigInteger> divisors = new ArrayList<BigInteger>(0);

    BigInteger[] firstPrimes = new BigInteger[4];
    firstPrimes[0] = new BigInteger("2");
    firstPrimes[1] = new BigInteger("3");
    firstPrimes[2] = new BigInteger("5");
    firstPrimes[3] = new BigInteger("7");

    // loop that test for first 4 prime numbers
    for (int l=0;l<4;l++){
        while ((number.mod(firstPrimes[l])).compareTo(BigInteger.ZERO) == 0) {
            number = number.divide(firstPrimes[l]);
            divisors.add(firstPrimes[l]);
        }
    }


    // loop that factors only numbers finishing by 1,3,7,9
    while (i.compareTo(number) == -1){

        // check for ending by 1
        if ((number.mod(i)).compareTo(BigInteger.ZERO) == 0) {
            while (number.mod(i).compareTo(BigInteger.ZERO) == 0){
                number = number.divide(i);
                divisors.add(i);
            }
        }
        else if ((number.mod(i)).compareTo(BigInteger.ZERO) != 0){
            i=i.add(firstPrimes[0]);
        }

        // check for ending by 3
        if ((number.mod(i)).compareTo(BigInteger.ZERO) == 0) {
            while (number.mod(i).compareTo(BigInteger.ZERO) == 0){
                number = number.divide(i);
                divisors.add(i);
            }
        }
        else if ((number.mod(i)).compareTo(BigInteger.ZERO) != 0){
            i=i.add(firstPrimes[0].multiply(firstPrimes[0]));
        }

        //check for ending by 7
        if ((number.mod(i)).compareTo(BigInteger.ZERO) == 0) {
            while (number.mod(i).compareTo(BigInteger.ZERO) == 0){
                number = number.divide(i);
                divisors.add(i);
            }
        }
        else if ((number.mod(i)).compareTo(BigInteger.ZERO) != 0){
            i=i.add(firstPrimes[0]);
        }

        // check for ending by 9
        if ((number.mod(i)).compareTo(BigInteger.ZERO) == 0) {
            while (number.mod(i).compareTo(BigInteger.ZERO) == 0){
                number = number.divide(i);
                divisors.add(i);
            }
        }
        else if ((number.mod(i)).compareTo(BigInteger.ZERO) != 0){
            i=i.add(firstPrimes[0]);
        }
    }

    // store prime factors into a BigInt array
    String[] strArrayDivisors = divisors.toString().replaceAll("\\[", "").replaceAll("\\]","").replaceAll("\\s","").split(",");

    BigInteger[] BigIntDivisors = new BigInteger[strArrayDivisors.length];

    for(int j=0;j<strArrayDivisors.length;j++){
        BigIntDivisors[j] = new BigInteger(strArrayDivisors[j]);
    }

    // returns all factors of "number"
    return BigIntDivisors;

}   
}

提前致谢。

Answer 1

首先，84738329279 = 41 * 61 * 61 * 555439。您的 41、61 和 61 是正确的。

但是当你的算法终止时，最后一个素数仍然在 number 中。您需要在末尾添加测试 number 的代码:如果它是 1，那么您已经完成，否则需要将其添加到 divisors 因此稍后会打印。