This is my first post in this forum and I'm a relative newbie to Python and to SPOJ.
I know this is an older thread but I wanted to give my quick two cents on this problem because I really pulled my hair out on this one (I probably should have done a tutorial problem). However, after cruising the forums, I get the impression that the CPython implementation probably was the cause of some of my grief. But I'll be the first to admit it was probably mostly due to my horrible submissions!
Yes, it is possible. And if you do it, give yourself a pat on the back (just look at the Python 3.2.3 submission statistics for PRIME1).
If memory serves me, I began with (more or less) brute force then moved to SOE (was about to move to something like Rabin-Miller or Fermat). Where I kept running into trouble, over and over, was the widening gap between the current value to check and the next composite number as the prime in question got larger. The Python profiler came in handy
I may be totally wrong here, but I was uneasy with some numbers getting flagged multiple times by SOE although in the end I don't think that was translating into huge slowdowns. I became acutely aware of inefficiencies in my algorithm and I got it to progressively run faster and faster on my box and at SPOJ (it was at least encouraging to see those TLEs going to WAs).
The fastest times are around a quarter of a second.
If anyone has any idea on how one could get those kind of times, I'd love to absorb some knowledge (threading? output options other than print? psyco? different sieve?).
Mine got to AC in 4.51 seconds, although on my box with large data sets I got it down to 0.69 seconds (and it was a Celeron).
So, some tips that may get someone just over the hump if trying to solve the Prime Generator problem (PRIME1) with Python on SPOJ:
-> Immutable, unordered data structures (think frozensets, their properties, and what can be done with them...)
-> Don't just use modulus for equality testing. Use that remainder to find more composites immediately.
-> Instead of using SOE to find primes from 2 up to square root of maximum, try using a list of primes ready-made (you already know the data set bounds).
-> Loops aren't healthy on this problem (I guess that's more of a generalization). Keep to a minimum.
-> sorted() will hurt you. range() will kill you.
Basically, my thinking turned from brute force to "OK, now what do I know about the result set after this step has completed?"
Use it to your advantage.
Of course, there is (most likely) room for much, much improvement on my algorithm given the best solution times, but I feel a certain sense of satisfaction that I didn't quit and solved a classical problem.
This n00b is definitely sticking with the tutorial problems next time around.
Best of luck to all!