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!)
>
One optimization, and this is only good for printing a list of primes,
is that you only need to test a number's divisibility by all *primes*
less than the square root of the number.
By keeping a list of the primes already calculated, I saw a 3 times
increase in speed counting all the prime numbers between 2 and one million:
# test all numbers below sqrt(n)
ebrunsonlx(~)$ time python primes.py
78498 primes below 1000000
real 0m14.496s
user 0m14.367s
sys 0m0.127s
# keeping a list of primes
ebrunsonlx(~)$ time python primes.py
78498 primes below 1000000
real 0m5.570s
user 0m5.551s
sys 0m0.017s
Here's the code I used:
primes = []
def isPrime1( n ):
s = n**.5
for d in xrange( 2, int(s)+1 ):
if not n%d:
return False
return True
def isPrime2( n ):
global primes
s = n**.5
for d in primes:
if d>s:
break
if not n%d:
return False
primes.append( n )
return True
That's just the most obvious optimization. I'd like to compare to the
performance of Sieve of Eratosthanes, but I don't feel like coding it.
> Could you please look at the program (attached) and advise possible
> optimisations or point me to possible resources that would help solve
> this challenge.
>
> Thanks,
>
> Boyks
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Tutor maillist - Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
