# Project Euler #124 – Java

You can see the problem here: Problem #124.

If there is one thing I learned from Project Euler, it’s that when you are dealing with prime factors, a sieve is usually the way to go. In the sieve, instead of taking away composite numbers, I’m implementing the “radical” function. Once the radical of each integer has been found, I just make a Radical class that would wrap the integer and its radical and sort the Radicals. Arrays.sort() will do all the hard work for me.

final int LIMIT = 100001; //array 0-based, but sieve is 1 based, so LIMIT = 100000 + 1 int[] rads = new int[LIMIT]; Arrays.fill(rads, 1); for (int i = 2; i < LIMIT; i++) { //if it's still 1, it's a prime and use it to modify the rest of the numbers if (rads[i] == 1) { rads[i] = i; for (int n = i + i; n < LIMIT; n += i) { rads[n] *= i; } } } Radical[] radicals = new Radical[LIMIT - 1]; //start converting the numbers and their radicals into a Radical Object //we don't want number 0 to be in the array, so we started converting at index 1 for (int i = 1; i < LIMIT; i++) { radicals[i - 1] = new Radical(rads[i], i); } //use Java's sort Arrays.sort(radicals); //then get the 10000 element (9999 used b/c array 0 based) System.out.println(radicals[9999].id);

The Radical class is shown below. It implements Comparable interface for sorting.The fields are public because this is a one-time class.

private static class Radical implements Comparable<Radical> { public int id, rad; public Radical(int rad, int id) { this.rad = rad; this.id = id; } public int compareTo(Radical radical) { if (this.rad > radical.rad) return 1; else if (this.rad < radical.rad) return -1; else { if (this.id == radical.id) return 0; return this.id > radical.id ? 1 : -1; } } }

Runs in ~100 miliseconds on my computer. Very easy and quick to code, so I can’t complain.

Well, every question from now on is going to be on fiendish difficulty, sigh. CU

## Leave a Reply