11

特定の数が持つ因子の数を返す関数をJavaで書き込もうとしています。

以下の制限を考慮に入れる必要があります。

  1. BigIntegerで行う必要があります
  2. 以前に生成された番号を保存することは許可されていないため、処理が増え、メモリが少なくなります（このように「アトキンのふるい」を使用することはできません） 。
  3. 負の数は無視できます。

これは私が今まで持っているものですが、それは非常に遅いです。

public static int getNumberOfFactors(BigInteger number) {
    // If the number is 1
    int numberOfFactors = 1;

    if (number.compareTo(BigInteger.ONE) <= 0)  {
        return numberOfFactors;
    }

    BigInteger boundry = number.divide(new BigInteger("2"));
    BigInteger counter = new BigInteger("2");

    while (counter.compareTo(boundry) <= 0) {
        if (number.mod(counter).compareTo(BigInteger.ZERO) == 0) {
            numberOfFactors++;
        }

        counter = counter.add(BigInteger.ONE);
    }

    // For the number it self
    numberOfFactors++;

    return numberOfFactors;
}
4

3 に答える 3

17

より速い解決策を提案できますが、まだ十分に速くはないと感じています。あなたのソリューションは で実行されO(n)、私のソリューションは で動作しO(sqrt(n))ます。

n = x i1 p1 * x i2 p2 * x i3 p3 * ... x ik pknが(つまり x i jはすべて異なる素数である)の素因数分解である場合、n は (p1 + 1) * (p2 + 1) * ... * (pk + 1) 合計の係数。

ここに解決策があります：

BigInteger x = new BigInteger("2");
long totalFactors = 1;
while (x.multiply(x).compareTo(number) <= 0) {
    int power = 0;
    while (number.mod(x).equals(BigInteger.ZERO)) {
        power++;
        number = number.divide(x);
    }
    totalFactors *= (power + 1);
    x = x.add(BigInteger.ONE);
}
if (!number.equals(BigInteger.ONE)) {
    totalFactors *= 2;
}
System.out.println("The total number of factors is: " + totalFactors);

これは、2 の場合を個別に検討し、x1 ではなく 2 に等しいステップ (奇数のみを繰り返す) を使用すると、さらに最適化できます。

また、私のコードでは、私が変更したものを保持し、反復するために別の変数numberを保持する方が適切であることに注意してください。numbernumber

このコードは、 2 64を超えない数に対してかなり高速に実行されると思います。

編集完全を期すために、回答に合理的に速い手段を追加します。以下のコメントに見られるように、テスト ケース 100000007 2に対して提案されたアルゴリズムのパフォーマンスについていくつかの測定を行いました。これは Betlista によって提案されました。

  • アルゴリズムをそのまま使用すると、私のマシンでは 57 秒かかります。
  • 奇数のみを考慮すると、時間は 28 秒に短縮されます
  • 二分探索を使用して見つけたwhile平方根と比較する終了条件のチェックを変更すると、所要時間は 22 秒に短縮されます。number
  • BigInteger最後に、すべてのs を切り替えてみるとlong、時間は 2 秒に短縮されました。number提案されたアルゴリズムは、 の範囲を超えると十分に高速に実行されlongないため、実装を次のように切り替えることが理にかなっています。long
于 2012-04-13T11:10:34.573 に答える
1

いくつかの改善：

  1. n / 2ではなく、sqrt（n）までチェックする必要があります。これにより、アルゴリズムはO（n）ではなくO（sqrt（n））になります。
  2. 2をチェックした後、奇数をチェックするだけで済みます。これにより、速度が2倍になります。
  3. 以前の数字を使用することはできませんが、既知の素数と少量のストレージを使用してふるいを作成できます。2、3は素数であるため、チェックする必要があるのは、12ではなく11、13、17、19、23だけです。 14,15,16,18。したがって、3からのデルタのパターンを保存できます：[+ 2、+ 4]、6ごとに繰り返します：
var deltas = [2,4];
var period = 6;
var val = 3;
var i=0;
while(val<sqrt(n)) {
    var idx = i%deltas.length; // i modulo num deltas
    val += deltas[idx];
    count += isFactor(n,val);
    // if reached end of deltas, add period
    if(idx == deltas.length-1) {
        val += period - deltas[idx];
    }
    ++i;
}

この結果が得られたら、それらが要因である場合は、明らかに2および/または3を追加する必要があります。

私は学校で退屈していたときに上記のパターンを解決しました。素数の任意のリストのパターンを計算できますが、収穫逓減の法則があります。追加するプライムごとに期間が長くなり、デルタのリストの長さが大幅に長くなります。したがって、既知の素数の長いリストの場合、デルタの非常に長いリストが得られ、速度はわずかに向上します。ただし、スピードアップがそれだけの価値があるかどうかをテストしてください。

値の既知の部分（示されている2値デルタを使用して2/3）をノックアウトするだけなので、これはstil O（sqrt（n））です。

ふるいと平方根の境界を組み合わせると、4 /（3 * sqrt（n））のスピードアップが得られるはずです。

[編集：期間-lastdeltaではなく、最後の値に期間を追加していました。ありがとう@Betlista]

于 2012-04-13T11:58:24.443 に答える
0

Boris Strandjev によって提案された最速のソリューションには、Java で大量の出力を生成するという問題があります。これは、Java で非常に大きな整数の約数を見つけるための最速のアルゴリズムです。

正常に実行されるコードは次のとおりです。

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

class ProductDivisors {

    public static BigInteger modulo=new BigInteger("1000000007");
    public static BigInteger solve=new BigInteger("1");
    public static BigInteger two=new BigInteger("2");
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        BigInteger prod=new BigInteger("1");
        while(N-->0){
            prod=sc.nextBigInteger();
            solve=solve.multiply(prod);
        }
        BigInteger x = new BigInteger("2");
        BigInteger total = new BigInteger("0");
        BigInteger totalFactors =new BigInteger("1");
        while (x.multiply(x).compareTo(solve) <= 0) {
            int power = 0;
            while (solve.mod(x).equals(BigInteger.ZERO)) {
                power++;
                solve = solve.divide(x);
            }
            total = new BigInteger(""+(power + 1));
            totalFactors=totalFactors.multiply(total);
            x = x.add(BigInteger.ONE);
        }
        if (!(solve.equals(BigInteger.ONE))) {
            totalFactors =totalFactors.multiply(two);
        }
        totalFactors=totalFactors.mod(modulo);
        System.out.println(totalFactors);
    }

}

このコードは通常、数値の配列を入力として取り、それによって乗算して大きな数値を生成します。そして、その後、約数をカウントするためのメインコード（ここでは数を含めて約数と見なされます）が実行され、出力が与えられます。

それが効率的な方法であることを願っており、必要に応じてエラーや追加を提案します。

于 2016-06-05T13:05:35.390 に答える