Oops, forgot to send to the list.
Hi! On 9/21/07, Boykie Mackay <[EMAIL PROTECTED]> wrote: > Ok,I have learnt how to generate prime numbers and how to 'split' > input.The above was to help me solve the second 'SPOJ' > challenge,PRIME1.The challenge can be found at > <https://www.spoj.pl/problems/classical/sort=0,start=0> ... > Could you please look at the program (attached) and advise possible > optimisations or point me to possible resources that would help solve > this challenge. Interesting problem! I've been experimenting a bit with it, but I'm not anywhere near the runtimes shown in the judge system... It definitely needs some kind of clever algorithm. My first thought was to use the sieve of Erastothenes (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) to generate the primes up front, but the maximum value of n is far too large. After that, I tried a combination: generate the primes up to sqrt(max N) and then divide larger numbers by those primes. If written in C, this runs fast enough (0.7 seconds on my laptop for a larger test case) but my Python implementation of the same algorithm still takes too long (about 7.5 seconds for the same test). I'd be very interested in hearing about how to write a Python program for this problem that can handle for example the input 1 999900000 1000000000 in less than a second. Regards, Kalle _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
