Project Euler 3 - Largest prime factor

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 primeFactors() {
        long n = 600851475143L;
        List 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.

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

StackExchange Code Review Q#162380, answer score: 2