What's wrong with my SPOJ solution

numerix wrote:Let's see, maybe I'll try a solution ...

For once I want to quote myself ...

The SPOJ prime number task had done it to me. After initially I didn't want to believe that the task with Python could even be accomplished in the maximum specified runtime of 6 s - after all, this is about the calculation of some 10,000 prime numbers from intervals of size 100,000 in the number range up to 1 billion - BlackJack has yes posted a link that leads to the fastest Python solutions and there you could marvel that it is actually possible to write a Python program that solves the problem in 0.41 s! * Could * mind you, because now there's an even faster one, and that's mine - :

Apart from the fact that one can even advance into these temporal areas, the most astonishing thing for me was that the solution (at least mine - I don't know that of the others) is not characterized by a terribly complex algorithm, but by an intelligent use of the Sieves of the Eratothenes. The core algorithm comprises just 10 lines of code.

At first I thought you needed some highly specialized expert algorithm and after some googling and wikipeding you will of course find them. But they were all so complicated for me that I didn't feel like thinking seriously about them. Instead, I spent a few hours with paper and pencil and experimented with the more than 2000 year old sieve des Eratothenes.

This enables a program with a runtime of well under 1 second that is approx. 30-40 lines long. For the last hundredths of a second you have to tinker for a while and try out different - apparently equivalent, but differently performing - variants of individual parts.

Thanks to Graf Wasserrutsche: It was fun!