Help with Project Euler #200?

Question

Possible Duplicate:
Need help solving Project Euler problem 200

Similar to this question

Project Euler Problem 200.

I wrote up a brute force solution in Java that takes several hours to run, and produced the first 500+ sqube numbers, which I thought should be enough. However, none of the answers from 190 to 210 seems to be the correct answer.

I'm wondering what I'm doing wrong here and how I could optimize this. Could the problem lie in BigInteger.isProbablePrime()?

I'm not sure if Stackoverflow is the best place to ask this, but I seem to be stuck. I've included my code and the generated data.

I'd really appreciate it if someone would give me some hints or pointers.

Edit: I've run the program again simply with using the first 500,000 prime numbers; took a day to run but produced the correct answer.

Answer 1

Aren't you supposed to think of a clever solution which doesn't take a day or even an hour to run? :D I think the problem is isProbablePrime, which doesn't guarantee that a number is a prime. It just says that a prime which was found could be a prime with a certain probability. You should use an algorithm which is certain that it has found a prime.

Answer 2

The first answer is incorrect because isProbablyPrime isn't always correct (hence the Probably). It's slow, in part, because you are using BigInteger. All the values involved will fit in a long. Why not use a long?

Answer 3

I'm a Project Euler administrator. Please do not post information that can spoil the problem for others, particularly code and answers, even half-functioning code. Please edit your question accordingly. EDIT: Thank you for doing so!

It's not unusual for solvers to use the web to search for information on solving a problem, and it would take away some fun if they stumbled upon such a spoiler. (Yes, I know there are sites with lots of solutions ready-made, but at least they're generally for the lowered numbered easy problems.)

We have forums for discussing difficulties with problems and getting hints, which are aggressively edited for spoilers.

Answer 4

There may be some simple refactorings you could do that would save some time. It seems that the bulk of the time is spent in the nested for loop. The order of magnitude is n squared. You could reduce the complexity by not nesting loops. Another problem is that you are finding more potential results than are required. You only need to find 200. The reason you are needing to find more is due to the fact that you are not finding the potential results in their numeric order. The TreeSet does keep the results in order, but the algorithm would be faster if it were able to stop when the 200th result was found.