3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – mtj May 4 '17 at 12:50
  • \$\begingroup\$ @mtj yes, only with odd numbers \$\endgroup\$ – Billal Begueradj May 4 '17 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.