Prime factorization of large numbers

Question

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

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).