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.

• mtj: As far as I understood, fermat factorization only works for odd numbers. Thus, from a concrete-problem point of view, yes, this solves the one problem presented here. In computer sciences I tend to prefer solutions which work for a whole class of problems, disregarding the concrete example input. Thus, as a programming solution, I think this is not as good as the previous examples.
• Billal BEGUERADJ: @mtj yes, only with odd numbers