# Project Euler #87 – Java

You can see the problem here: Problem #87.

I just chose an easy problem to do because I have no idea how to do the other problems. Well, at least I can’t think of a solution within one minute of reading it. I’m lazy that way. This problem is easy enough. I already created a class representing prime sieve, and all you need to do is create combinations of prime squares, cubes, and fourth powers and keep track those with sums below 50,000,000. The tricky (although NOT that tricky) part of the question is to realize there are ways to reach the same sum with different combinations, so I just made a HashSet to catch the duplicate sums.

int LIMIT = 50000000; int[] primes = new EratosthenesSieve(10000).toArray(); LinkedList<Integer> squares = new LinkedList<Integer>(), LinkedList<Integer> cubes = new LinkedList<Integer>(), LinkedList<Integer> fours = new LinkedList<Integer>(); //fill the LinkedLists with the prime squares, cubes, and fourth powers int temp = 4, count = 0; while (temp < LIMIT) { squares.add(temp); temp = primes[++count] * primes[count]; } temp = 8; count = 0; while (temp < LIMIT) { cubes.add(temp); temp = primes[++count] * squares.get(count); } temp = 16; count = 0; while (temp < LIMIT) { fours.add(temp); temp = primes[++count] * cubes.get(count); } HashSet<Integer> noDups = new HashSet<Integer>(); for (Integer square : squares) { for (Integer cube : cubes) { for (Integer four : fours) { temp = square + cube + four; if (temp > LIMIT) { break; } else { noDups.add(temp); } } } } System.out.println(noDups.size());

Runs in about 1.7 seconds on my computer.

This seems slow for what it’s doing, so I decided to optimize it a little. Instead of using a HashSet, I decided to put all the numbers inside an array, and after getting all the sums, sort it and remove the duplicates (they will be adjacent to each other), and count the number of remaining elements. Surprisingly, the sort and remove method actually run faster than HashSet. This is what I came up with (I wrote an ArraysUtils class containing all the removeDuplicates stuff):

int LIMIT = 50000000; int[] primes = new EratosthenesSieve(10000).toArray(); LinkedList<Integer> squares = new LinkedList<Integer>(), LinkedList<Integer> cubes = new LinkedList<Integer>(), LinkedList<Integer> fours = new LinkedList<Integer>(); //fill the LinkedLists with the prime squares, cubes, and fourth powers int temp = 4, count = 0; while (temp < LIMIT) { squares.add(temp); temp = primes[++count] * primes[count]; } temp = 8; count = 0; while (temp < LIMIT) { cubes.add(temp); //save a multiplication, not sure if it helps though, with the unboxing and method overhead temp = primes[++count] * squares.get(count); } temp = 16; count = 0; while (temp < LIMIT) { fours.add(temp); //save two multiplications, not sure if it helps though, with the unboxing and method overhead temp = primes[++count] * cubes.get(count); } //hard coded so the array can hold enough sums, in real life I progressively increase the size until it fits int[] sums = new int[1200000]; count = -1; for (Integer square : squares) { for (Integer cube : cubes) { for (Integer four : fours) { temp = square + cube + four; if (temp > LIMIT) { break; } else { sums[++count] = temp; } } } } ArraysUtils.sortAndRemoveDuplicates(sums); System.out.println(sums.length);

Runs about ^400 milliseconds on my computer now. Note that more autoboxing in the first code so that needs to be taking into account, but apparently if you don’t care about the order of the elements, sorting an array and then remove the (adjacent) duplicate elements are way faster than a HashSet, interesting…

80 questions complete now, 20 more to go. It’s probably going to take me half a year though, sigh. CU

## Leave a Reply