My first idea was Sieve of Eratosthenes, too. But obviously my coding was not optimal and it exceeded 6s time limit. Then I googled it. Sounds like Miller-Rabin Testing is a much more serious solution. http://www.cnblogs.com/feature/articles/1824667.html It is based on Fermat Little Theory and property of square root of unity. But the practical use of this method was not satisfactory - it is not 100% accurate - flawness with P of 1/(4^k) - k the MR testing times.
But it is only #2 in SPOJ, it doesn‘t require too much number theory stuff, and Sieve of Eratosthenes works - as long you code it in smart way. Check it out here: http://jamie-wong.com/2009/11/12/spoj-problem-2-prime-generator/
原文：http://www.cnblogs.com/tonix/p/3537547.html