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

[Kent Johnson]

Boykie Mackay 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> 
> 
> I have written my solution and tested it and it works fine,but
> unfortunately it is times out when tested by 'SPOJ'.I don't know whether
> it times out because it is inherently slow or because a certain
> condition takes it into endless loops.I think it is simply because it
> needs further optimisation.I have researched as much as I could but
> can't find any way to improve the speed of the program (problem with
> being a newbie is you don't know what you don't know!)

Computing prime numbers is an area where picking a good algorithm is 
important. This page might help:
http://en.wikipedia.org/wiki/Prime_number#Location_of_prime_numbers

Depending on what ranges your program is working with, a sieve algorithm 
might be faster than checking each number individually.

Python is not very fast at raw arithmetic. The top 20 submissions to 
this problem are in C and C++ and have times <= 0.03. The top Python 
program has a time of .41, so you are starting out at a disadvantage.

If SPOJ allows you to use psyco then do so, that will make a big difference.
http://psyco.sourceforge.net/

Kent