Project Euler 3 - Largest prime factor

Question

Problem 3 - Largest prime factor

Exercise

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

My solution

package pl.hubot.projecteuler.problem3;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.print(Collections.max(primeFactors()));
    }

    private static List<Long> primeFactors() {
        long n = 600851475143L;
        List<Long> factors = new ArrayList<>();
        for (long i = 2; i <= n; i++) {
            while (n % i == 0) {
                factors.add(i);
                n /= i;
            }
        }
        return factors;
    }
}

I would like ask review for my code and possible improvements. I am interested how is performance of my code.

Answer 1

Get rid of the list. No, really, it's as simple as that. The sequence of is in factors will be non-decreasing, so essentially you could switch

System.out.print(Collections.max(primeFactors()));

with

List<Long> factors = primeFactors();
System.out.print(factors.get(factors.size() - 1));

While the list for prime factors might come in handy for other challenges, you're just interested in the largest, so it's fine to return just a single value:

private static long largestPrimeFactor(long n) {
    long largest = -1;
    for (long i = 2; i <= n; i++) {
        while (n % i == 0) {
            largest = i;
            n /= i;
        }
    }
    return largest;
}

Since you're interested in performance, you probably want to split the for into two parts to skip the unneeded even integers:

private static long largestPrimeFactor(long n) {
    long largest = -1;

    while(n % 2 == 0) {
        largest = 2;
        n /= 2;
    }

    for (long i = 3; i <= n; i = i + 2) {
        while (n % i == 0) {
            largest = i;
            n /= i;
        }
    }
    return largest;
}

Other than that, well done, and the correct approach. But just as in your previous code, ask yourself whether you really need the whole collection.

Answer 2

You should choose more efficient and fast methods.

In case the number to factor has two factors close to its square root then Fermat factorization is your best friend:

public class FermatFactorization {

    private long largeNumber = 600851475143L;

    public  double computeLargestFactor() { 
        double a =  Math.ceil(Math.sqrt((double)this.largeNumber));
        double b = Math.pow(a, 2) - (double)this.largeNumber;
        while(b != Math.sqrt(a)){
            a += 1;
            b = Math.pow(a, 2) - (double)this.largeNumber;
        }       
        return a - Math.sqrt(b);        
    }

    public static void main(String[] args) {        
        FermatFactorization fermatFactorization = new FermatFactorization();
        System.out.println(fermatFactorization.computeLargestFactor()); 

    }    
}

You can even easily improve this approach.

If you need to resolve your problem for a serious requirement (at workplace, for instance), then you could opt to implement quadratic sieve algorithm using parallel processing.

You may be interested in reading factoring large integers paper.