大数的素数因子化
我想找到小于10 ^ 12的大数的素数因子分解。 我有这个代码（在java中）：
public static List primeFactors(long numbers) { long n = numbers; List factors = new ArrayList(); for (long i = 2; i 1) { factors.add(n); } return factors; } 首先，上述算法的复杂性是什么？我很难找到它？
对于素数较大的数字来说，它也会太慢。
是否有更好的算法，或者如何优化这个算法？
如果你想对许多大数进行分解，那么你可能最好先找到最多为sqrt(n)的素数（例如使用Sieve of Eratosthenes ）。 然后你必须只检查那些素数是否是因子而不是测试所有i <= sqrt(n) 。
复杂度为O(sqrt(n)) 。 在sqrt(n)之后检查数字是没有意义的。
这意味着对于10^12 ，最多需要1 000 000次迭代，这并不慢。
对大数进行因子分解是一个难题，这也是加密算法使用大素数因子使加密难以破解的部分原因。
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 primeFactors(long n) { List factors = new ArrayList (); 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 ms内分解。
一个更好的算法可能是以下搜索素数（我的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); }