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

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() {

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

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);
}
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

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;