In doing some testing of different but simple algorithms for getting a
list of prime numbers, I ended up getting some results that seem a bit
contradictory. Given the following test program (testPrimes.py) with
two algorithms that both check for primes by testing only odd numbers
using factors up to the square root of the value, where Primes1 is based
on all of the existing primes so far, and Primes2 is based on all odd
numbers, I would expect that, as the number of primes we check gets
larger, that Primes1 should get more & more efficient (since it should
be performing less tests for each number). However the ratio seems to
be relatively consistent. Another thing that is interesting is that
once I tested up to n=200000, I got an exception in Primes2. I added
the long typecast in the 'limit=' statement for both versions and the
resulting improvements were strange: Primes1 runs 10-20% SLOWER, and
Primes2 runs about 50% FASTER!
I am not looking to come up with the most optimized solution to prime
numbers here. Primes1 is faster than Primes2 as I would expect and it
is clear, relatively elegant, and sufficient for me. However, I can't
figure out why the ratio doesn't improve with size, and the strange
results of the long typecast, and I would like to be able to understand
what is causing their behavior. Any ideas? Thanks,
--
Greg
#------------------------------------------------------------
import math, time
def Primes1(y):
primes = [3]
for p in range(5, y, 2):
limit = math.sqrt(p) # or: long(math.sqrt( p))
for factor in primes:
if factor > limit: # then number is prime
primes.append(p )
break
elif p % factor == 0: # then it's *not* prime
break
return [2] + primes
def Primes2(y):
primes = [2,3]
for p in range(5, y, 2):
limit = math.sqrt(p) + 1 # or: long(math.sqrt( p)) + 1
# check one extra to let us see if there were no factors
for n in range(3,limit+3 ,2):
if p % n == 0: # then it's *not* prime
break
if n > limit:
primes.append(p ) # then number is prime
return primes
if __name__ == "__main__":
n=100000
tb = time.time()
l1 = Primes1(n)
t1 = time.time() - tb
print 'Primes1: %s primes up to %s in %5.3f secs' % (len(l1), n, t1)
tb = time.time()
l2 = Primes2(n)
t2 = time.time() - tb
print 'Primes2: %s primes up to %s in %5.3f secs' % (len(l2), n, t2)
print 'ratio: %5.2f' % tt
#------------------------------------------------------------
I get the following results (avg for 3 runs each using Python 2.3.2 on
Win XP Pro):
n=50000 n=100000 n=200000
w/out long:
-----------
Primes1: 0.41 0.95 2.24
Primes2: 1.90 4.21 9.28
Ratio: 4.63 4.42 4.14
w/ long:
-----------
Primes1: 0.48 1.12 2.60
Primes2: 0.84 2.04 4.75
Ratio: 1.75 1.82 1.82
list of prime numbers, I ended up getting some results that seem a bit
contradictory. Given the following test program (testPrimes.py) with
two algorithms that both check for primes by testing only odd numbers
using factors up to the square root of the value, where Primes1 is based
on all of the existing primes so far, and Primes2 is based on all odd
numbers, I would expect that, as the number of primes we check gets
larger, that Primes1 should get more & more efficient (since it should
be performing less tests for each number). However the ratio seems to
be relatively consistent. Another thing that is interesting is that
once I tested up to n=200000, I got an exception in Primes2. I added
the long typecast in the 'limit=' statement for both versions and the
resulting improvements were strange: Primes1 runs 10-20% SLOWER, and
Primes2 runs about 50% FASTER!
I am not looking to come up with the most optimized solution to prime
numbers here. Primes1 is faster than Primes2 as I would expect and it
is clear, relatively elegant, and sufficient for me. However, I can't
figure out why the ratio doesn't improve with size, and the strange
results of the long typecast, and I would like to be able to understand
what is causing their behavior. Any ideas? Thanks,
--
Greg
#------------------------------------------------------------
import math, time
def Primes1(y):
primes = [3]
for p in range(5, y, 2):
limit = math.sqrt(p) # or: long(math.sqrt( p))
for factor in primes:
if factor > limit: # then number is prime
primes.append(p )
break
elif p % factor == 0: # then it's *not* prime
break
return [2] + primes
def Primes2(y):
primes = [2,3]
for p in range(5, y, 2):
limit = math.sqrt(p) + 1 # or: long(math.sqrt( p)) + 1
# check one extra to let us see if there were no factors
for n in range(3,limit+3 ,2):
if p % n == 0: # then it's *not* prime
break
if n > limit:
primes.append(p ) # then number is prime
return primes
if __name__ == "__main__":
n=100000
tb = time.time()
l1 = Primes1(n)
t1 = time.time() - tb
print 'Primes1: %s primes up to %s in %5.3f secs' % (len(l1), n, t1)
tb = time.time()
l2 = Primes2(n)
t2 = time.time() - tb
print 'Primes2: %s primes up to %s in %5.3f secs' % (len(l2), n, t2)
print 'ratio: %5.2f' % tt
#------------------------------------------------------------
I get the following results (avg for 3 runs each using Python 2.3.2 on
Win XP Pro):
n=50000 n=100000 n=200000
w/out long:
-----------
Primes1: 0.41 0.95 2.24
Primes2: 1.90 4.21 9.28
Ratio: 4.63 4.42 4.14
w/ long:
-----------
Primes1: 0.48 1.12 2.60
Primes2: 0.84 2.04 4.75
Ratio: 1.75 1.82 1.82
Comment