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

[Kalle Svensson]

Oops, forgot to send to the list.


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...

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