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)（例如使用埃拉托色尼筛）。然后你只需要检查这些素数是否是因数，而不是测试 all 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 回答
5

因式分解大数是一个难题，这也是加密算法使用大素数的因数来使加密难以破解的部分原因。

public static void main(String... args)  {
    int nums = 100;
    for (int i = 0; i < nums; i++) {
        long start = System.nanoTime();
        primeFactors(Long.MAX_VALUE - i);
        long time = System.nanoTime() - start;
        if (time > 100e6)
            System.out.println((Long.MAX_VALUE-i) + " took "+time/1000000+" ms.");
    }
}

public static List<Long> primeFactors(long n) {
    List<Long> factors = new ArrayList<Long>();
    while (n % 2 == 0 && n > 0) {
        factors.add(2L);
        n /= 2;
    }

    for (long i = 3; i * i <= n; i+=2) {
        while (n % i == 0) {
            factors.add(i);
            n /= i;
        }
    }
    if (n > 1)
        factors.add(n);

    return factors;
}

印刷

9223372036854775806 took 3902 ms.
9223372036854775805 took 287 ms.
9223372036854775804 took 8356 ms.
9223372036854775797 took 9519 ms.
9223372036854775796 took 1507 ms.
9223372036854775794 took 111 ms.
9223372036854775788 took 184 ms.

如果将 Long.MAX_VALUE 替换为 1000000000000L，它们都会在 20 毫秒内分解。

于 2012-09-03T17:53:12.700 回答
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 回答