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 _______________________________________________ Tutor maillist - [email protected] http://mail.python.org/mailman/listinfo/tutor
