# 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