Primary factorization of large numbers

Question

I want to find a simple factorization of large numbers less than 10 ^ 12. I got this code (in 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; } 

First of all, what is the complexity of the above algorithm? I am having difficulty finding it.

Also for large numbers it will be too slow.

Is there a better algorithm, or how to optimize this algorithm?

Answer 1

If you want to decompose many large numbers, then you might be better off finding primes before sqrt(n) (for example, using the Sieve of Eratosthenes ). Then you should check only if these primes are factors, and not testing all i <= sqrt(n) .

Answer 2

Complexity O(sqrt(n)) . It makes no sense to check the numbers after sqrt(n) .

This means that for 10^12 it will take no more 1 000 000 iterations, which is not slow.

Answer 3

Factoring large numbers is a difficult problem, in part because encryption algorithms use large prime factors to make encryption difficult.

 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; } 

prints

 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. 

If you replace Long.MAX_VALUE with 1000000000000L, all of them are divided by less than 20 ms.

Answer 4

A better algorithm might be the following for finding prime numbers (my java is rusty, so it will probably need some tweaking to compile it).

 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); }