13
\$\begingroup\$

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<Problem<?>> 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<Problem<?>> {
        @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<List<Long>> {
    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) {
            PrimeGenerator primeGenerator = new PrimeGenerator();
            while (primeGenerator.hasNext()) {
                long prime = primeGenerator.nextLong();
                if (numberCopy % prime == 0) {
                    result.add(prime);
                    numberCopy /= prime;
                    break;
                }
            }
        }
    }

    @Override
    public String getName() {
        return "Problem 3";
    }
}

public class PrimeGenerator implements PrimitiveIterator.OfLong {
    private final static LongNode HEAD_NODE = new LongNode(2);

    private LongNode lastNode = HEAD_NODE;
    private long current = 2;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public long nextLong() {
        if (lastNode.value == current) {
            if (lastNode.next != null) {
                long old = lastNode.value;
                lastNode = lastNode.next;
                current = lastNode.value;
                return old;
            }
            return current++;
        }
        while (true) {
            if (isPrime(current)) {
                appendNode(current);
                return current++;
            }
            current++;
        }
    }

    private boolean isPrime(final long number) {        
        LongNode prime = HEAD_NODE;
        while (prime != null && prime.value <= number) {
            if (number % prime.value == 0) {
                return false;
            }
            prime = prime.next;
        }
        return true;
    }

    private void appendNode(final long value) {
        LongNode newNode = new LongNode(value);
        couple(lastNode, newNode);
        lastNode = newNode;
    }

    private void couple(final LongNode first, final LongNode second) {
        first.next = second;
        second.previous = first;
    } 

    private static class LongNode {
        public final long value;

        public LongNode previous;
        public LongNode next;

        public LongNode(final long value) {
            this.value = value;
        }
    }

    public static LongStream infiniteStream() {
        return StreamSupport.longStream(
                Spliterators.spliteratorUnknownSize(new PrimeGenerator(), Spliterator.ORDERED | Spliterator.IMMUTABLE), false
        );
    }
}

Java 8 remarks:

  • I've not used the PrimeGenerator.infiniteStream() in this answer, so no need to consider it.
  • ProjectEuler class is just given for convenience.
  • PrimiteIterator.OfLong is a primitive wrapper for Java 7 equivalent Iterator<Long>.

The idea I've used for this exercise was that I need a list of prime numbers. And everytime the original number modulo that prime was zero, I would add a factor to the list and divide the number by that prime.

Other remark on the speed, which I think is pretty interesting, I also ran code that sums up the first million prime numbers.

  • When properly benchmarking, with 10000 warmups and 10000 real tests, the time was averaged 7.5ms.
  • However with just one real test, it is still running after a considerate amount of time, at least an hour I think.
\$\endgroup\$
6
\$\begingroup\$

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

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

\$\endgroup\$
6
\$\begingroup\$

Some general observations.

  • I agree with Uri that your use of the custom Linked-List is cumbersome. It also leads you to have redundant code, like you have an unused 'previous' node... Uri is right to syggest a List for this, but I would recommend an ArrayList as it will be faster (because it will use half the memory as it has half the number of Objects).... actually, like most times, I would prefer the use of an array of long[] with a size parameter to track how large it is, and then resize as needed. That will use about 10% of the memory of the same data in the LinkedList, and about 20% of the data in your LinkNode system. Despite what many people believe, Java performance in many ways is related to the memory footprint. Smaller data is faster.

  • Your class is not thread-safe. This is a problem for using with Java8. If your PrimeGenerator is linked to a parallel Lambda then you will be in trouble. in particular, the private final static LongNode HEAD_NODE = new LongNode(2); is going to mean that all threads will try to modify the same linked structure.

  • I am aware that you have changed the problem from being 'find the largest' to 'find them all', but, you should consider a system where you start from the highest prime that could possibly be a factor (Math.sqrt(value)) and work backwards. This will save a lot of computation:

    while (numberCopy > 1) {
        long root = (long)Math.sqrt(numberCopy);
        for (long prime : PrimesGenerator.descendingFrom(root)) {
            if (numberCopy % prime == 0) {
                numberCopy /= prime;
                factors.add(prime);
            }
        }
    }
    
\$\endgroup\$
2
\$\begingroup\$

A few comments:

  • I agree that using a custom implementation of a LinkedList without a need to is a bad practice.
  • Public mutable fields are bad.
  • It is considered pedantic to add final to arguments.
  • I don't like your method of generating primes. You check if a number is prime by iterating over all smaller primes. Two possible improvements would be to iterate only over primes in range [1, \sqrt{x}], or to use a fancy primality test like Miller-Rabin. But a faster and easier approach would be to use Seive of Eratosthenes to generate primes.
\$\endgroup\$

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.