Skip to content
April 9, 2011 / oop123

Project Euler #187 – Java

You can see the problem here: Problem #187.

I am just now finding simple questions to get to level 3. Unfair and cheating, yes, but I don’t care. I don’t think there is too much simple problems anyway, so I will take what I can get.

This question is really easy. A number with two prime factors are always unique, so there is no need to get the actual numbers to check for uniqueness. I just need to count the numbers of prime combinations, easy peasy.

//for some reason, 50000000 would cause ArrayIndexOutOfBound, so I choose a slightly higher size for the sieve
int[] primes = new EratosthenesSieve(51000000).toArray();
int limit, count = 0;

for (int i = 0; primes[i] < 10000 /* only need to count from primes up to sqrt of 1 * 10^8 */; i++) {
	limit = 100000000 / primes[i];

	for (int j = i; primes[j] <= limit; j++) {
		++count;
	}
}
System.out.println(count);

Runs in ~1 second on my computer. %90+ of the time was taken in the generation of the sieve and primes array; otherwise, this is a really fast question.

Some high ranking questions can be pretty easy, got to look out for them. 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: