3

10 ^ 12 未満の大きな数の素因数分解を見つけたいです。私はこのコードを取得しました（Javaで）：

public static List<Long> primeFactors(long numbers) {
        long n = numbers;
        List<Long> factors = new ArrayList<Long>();
        for (long i = 2; i <= n / i; i++) {
            while (n % i == 0) {
                factors.add(i);
                n /= i;
            }
        }
        if (n > 1) {
            factors.add(n);
        }
        return factors;
    }

まず第一に、上記のアルゴリズムの複雑さは??見つけるのに苦労しています??

また、素数である大きな数には遅すぎます。

より良いアルゴリズムはありますか、それともこのアルゴリズムを最適化する方法はありますか??

4

4 に答える 4

16

多くの大きな数を因数分解したい場合は、最初に までの素数を見つけたほうがよいかもしれませんsqrt(n)(たとえば、エラトステネスのふるいを使用します)。次に、すべてをテストするのではなく、それらの素数が因数であるかどうかのみを確認する必要がありますi <= sqrt(n)。

于 2012-09-03T17:39:36.777 に答える
5

複雑さはO(sqrt(n)). の後に数字をチェックしても意味がありませんsqrt(n)。

これは、 の場合、遅くない10^12最大1 000 000反復回数しかかからないことを意味します。

于 2012-09-03T17:29:44.380 に答える
1

素数を検索するためのより良いアルゴリズムは次のようになります（私のJavaは錆びているので、コンパイルするにはおそらく多少の調整が必要になります）。

if (number % 2)
   factors.append(2)
if (number % 3)
   factors.append(3)

for(int n = 0; n < sqrt(number)/6; n++)
{
   if (number % (6 * n + 1))
      factors.append(6 * n + 1);
   if (number % (6 * n - 1))
      factors.append(6 * n - 1);
}
于 2012-09-05T05:06:02.793 に答える