0

数値を素因数分解するプログラムをコーディングしています。プログラムは次のように動作します。

1) 因数分解する数値を入力します (これを「inputNumber」と呼びます)

2) inputNumber を 2、3、5、および 7 (最初の 4 つの素数) で割り切れるかどうかをテストします。これらのいずれかで割れる場合は、できる限り何度でも割ることができます (つまり、12 を 2 で 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 で終わる数をテストする必要もありません。

これは非常に巧妙なアルゴリズムです。なぜなら、1 つの数値を次々にテストして数値を因数分解するよりもはるかに高速だからです。実際、すべての数値の 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;

}   
}

前もって感謝します。

4

1 に答える 1

1

まず、84738329279 = 41 * 61 * 61 * 555439. あなたの 41、61、61 は正しいです。

しかし、アルゴリズムが終了すると、最後の素数がまだ に残っていnumberます。number最後にテストするコードを追加する必要があり1ますdivisors。

于 2013-07-25T21:25:42.230 に答える