This is a nice little problem, I had fun solving it.

For those of us who are familiar with TopCoder, CodeForces or, perhaps, ACM ICPC, this should be daily bread and butter on prime numbers and data structures :)

Here is my solution if you are curious: https://gist.github.com/Slava/74276f5b7889a1d68a71 - computes the result in 400ms

Edit: hah, looking at the problems discussion board I took a very bruteforce approach, other people solved utilizing math, I used priority_queue for no particular reason :)