[Tutor] Optimisation of prime number program (cont. from finding prime numbers)

[Kalle Svensson]

Hi!

Just a followup on this:

On 9/21/07, Kalle Svensson <kalle.svensson at gmail.com> wrote:
> Hi!
>
> On 9/21/07, Boykie Mackay <boykie.mackay at gmail.com> 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