Hi! Just a followup on this:
On 9/21/07, Kalle Svensson <[EMAIL PROTECTED]> wrote: > 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... After quite a bit of experimentation, I finally managed to write a program that was accepted by the judge system. It's a C++ implementation of the deterministic Miller-Rabin algorithm. My Python implementation of the same algorithm is still too slow, though. Has anyone managed to write a fast enough Python program? The problem: https://www.spoj.pl/problems/PRIME1/ Miller-Rabin: http://en.wikipedia.org/wiki/Miller-Rabin_primality_test Regards, Kalle _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
