Skip to content
April 22, 2011 / oop123

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: