Project Euler - Problem 3

euler.java

package euler;

public class Prime {

    public static void main(String[] args) { 
        int n = 100000;

        // initially assume all integers are prime
        boolean[] isPrime = new boolean[n+1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        for (int factor = 2; factor*factor <= n; factor++) {

            // if factor is prime, then mark multiples of factor as non-prime
            // suffices to consider multiples factor, factor+1, ...,  n/factor
            if (isPrime[factor]) {
                for (int j = factor; factor*j <= n; j++) {
                    isPrime[factor*j] = false;
                }
            }
        }
        
        long x = 600851475143L;
        
        for (int i = 0; i < isPrime.length; i++) {
			if (!isPrime[i]) continue;
			if (x % i == 0) {
				x /= i;
				System.out.println(i);
			}
		}
    }
}