Prime factorization of large numbers [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 7 years ago.

I want to find the prime 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 difficulties finding it ??

Also it will be too slow for large numbers that are prime .

Is there are better algorithm , or else how to optimize this algo ??

Answer 1

The complexity is O(sqrt(n)). There is no sense in checking numbers after sqrt(n).

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

Answer 2

Factorising large numbers is hard problem which is partly why encryption algos use factors of large prime numbers to make the encryption difficult to crack.

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 they all factorize under 20 ms.

Answer 3

If you want to factorize many large numbers, then you might be better off first finding the prime numbers up to sqrt(n) (e.g. using Sieve of Eratosthenes). Then you have to check only whether those prime numbers are factors instead of testing all i <= sqrt(n).

Answer 4

A better algorithm might be the following for searching for primes (my java is rusty, so some tweaking will probably be needed to get it to compile).

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