HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Project Euler "Largest prime factor" (#3) in Java

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
javalargestprojecteulerfactorprime

Problem

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

What is the largest prime factor of the number 600851475143 ?

I wrote the following code with help of some Java 8, I'll explain the equivalent to Java 7 under the code. I'd like general comments. One note to give up ahead is that I did not write a program that gives the largest prime factor, but one that gives all prime factors.

public class ProjectEuler {
    private final static int WARMUP_COUNT = 0;
    private final static int REAL_COUNT = 1;

    private final List> problems = new ArrayList<>();

    private void init() {
        problems.add(new Problem1());
        problems.add(new Problem2());
        problems.add(new Problem3(600851475143L));

        process();
    }

    private void process() {
        problems.stream().forEachOrdered(new ProblemConsumer());
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        new ProjectEuler().init();
    }

    private class ProblemConsumer implements Consumer> {
        @Override
        public void accept(Problem problem) {            
            for (int i = 0; i < WARMUP_COUNT; i++) {
                problem.run();
            }
            System.gc();

            long start = System.nanoTime();
            for (int i = 0; i < REAL_COUNT; i++) {
                problem.run();
            }
            double average = (System.nanoTime() - start) * 1.0d / REAL_COUNT;

            String result = problem.getResult();

            System.out.println(problem.getName() + ": " + result + " (" + String.format("%.5f", (average / 1_000_000.0)) + " ms" + ")");
        }        
    }
}


```
public class Problem3 extends Problem> {
private final long number;

public Problem3(final long number) {
this.number = number;
}

@Override
public void run() {
long numberCopy = number;
result = new ArrayList<>();
while (numberCopy > 1) {
PrimeG

Solution

Actually, your iterator is two iterators - one for the known primes (from previous 'warmups'), and one for unknown primes. Your known prime iterator's choice of implementation looks a bit cumbersome - you could have used a simple list of Long, and iterate over it:

private final static List KNOWN_PRIMES = new LinkedList();

private Iterator knownPrimeIterator = KNOWN_PRIMES.iterator();
private long lastResult = 1;

public long nextLong() {
    if (knownPrimeIterator != null && knownPrimeIterator.hasNext()) {
        lastResult = knownPrimeIterator.next().toLong();
    } else {
        knownPrimeIterator = null;
        lastResult = findNextPrime(lastResult+1);
        KNOWN_PRIMES.add(new Long(lastResult));
    }
    return lastResult;
}

private long findNextPrime(long startFrom) {
    // whatever here...
}


Regarding your benchmark, I believe that 'warming up' is a little like cheating... you are caching the results in your static array. If you wanted to have a high-performant solution, you could have pre-calculated the first 1,000,000 primes, saved them to a file, and read them at the beginning of the procedure... :P

Code Snippets

private final static List<Long> KNOWN_PRIMES = new LinkedList<Long>();

private Iterator<Long> knownPrimeIterator = KNOWN_PRIMES.iterator();
private long lastResult = 1;

public long nextLong() {
    if (knownPrimeIterator != null && knownPrimeIterator.hasNext()) {
        lastResult = knownPrimeIterator.next().toLong();
    } else {
        knownPrimeIterator = null;
        lastResult = findNextPrime(lastResult+1);
        KNOWN_PRIMES.add(new Long(lastResult));
    }
    return lastResult;
}

private long findNextPrime(long startFrom) {
    // whatever here...
}

Context

StackExchange Code Review Q#42609, answer score: 6

Revisions (0)

No revisions yet.