public
Created — forked from bobmurder/primes.py

  • Download Gist
primes.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
#!/usr/bin/env python
import time
from math import sqrt
 
def sieve(stop):
'''
That sieve of eratosthenes thing. Implemented directly from the
pseudocode found here:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Implementation
'''
stop += 1
counter = 0
num_list = range(2, stop)
for i in num_list:
counter += 1
if i:
args = (i * 2, stop, i)
for j in range(*args):
counter += 1
idx = j - 2
num_list[idx] = False
primes = [n for n in num_list if n]
return primes, counter
 
def trial_div(stop, lim_sqrt=False, counter=0):
'''
trial divide each candidate by each known prime
OR if lim_sqrt=True is passed as an argument,
trial divide each candidate by each known prime < sqrt(candidate)
'''
counter = 0
start, step = 3, 2
args = start, stop, step
primes = [2]
for n in range(*args):
counter += 1
prime = True
for p in primes:
# assume prime is True
counter += 1
# limit trial division to known primes < sqrt(n)
if lim_sqrt:
if not p <= sqrt(n):
break
if n % p == 0:
prime = False
# trial divide each candidate by all known primes
else:
if n % p == 0:
prime = False
# if the prime flag wasn't changed
if prime:
primes.append(n)
return primes, counter
 
 
def format_output(name, stop, primes, steps, elapsed):
'''
Return a formatted string with result data filled in
'''
return '\n'.join(
('------------------------------',
"%s" % name,
"",
"primes found: %s" % len(primes),
"steps taken: %s" % steps,
"running time: %ss" % elapsed,
"",
)
)
 
def prime_wrapper(stop, f, arg=None):
'''
A wrapper function for calling each prime function and
timing how long it takes. It calls trial_div(max_prime, lim_sqrt=True)
if arg is True
'''
then = time.time()
if arg:
primes, steps = f(stop, arg)
else:
primes, steps = f(stop)
now = time.time()
elapsed = str(now - then)[:8]
return primes, steps, elapsed
 
if __name__ == '__main__':
import sys
# CSV = True for csv-ish output in the following format:
# 'name','max prime candidate','time'
CSV = False
# ugly ass separator
sep = '##################################################'
 
# results are printed out in the order of these tuples
# each element is (func, arg, name)
prime_funcs = [(sieve, None, 'sieve')]
(trial_div, True, 'trial division - sqrt'),
(trial_div, None, 'trial division - all')]
 
# find 2 to n primes for each max candidate in this list
max_prime_list = [1000, 5000, 10000, 25000, 50000]
 
# or pass an argument in to check all 3 methods vs one range of numbers
if len(sys.argv) > 1 and sys.argv[1].isdigit():
max_prime_list = [int(sys.argv[1])]
 
if CSV:
stat_data = []
 
for max_prime in max_prime_list:
# output header
print ''.join([sep, '\n', 'Primes from 2 to %s' % max_prime, '\n'])
# iterate over the prime_funcs list from above and call
# the wrapper function with once with each prime function
# then output the results.
for prime_func, arg, name in prime_funcs:
stats = prime_wrapper(max_prime, prime_func, arg)
if CSV:
stat_data.append((name, str(max_prime), str(stats[2])))
print format_output(name, max_prime, *stats)
 
if CSV:
for data in stat_data:
print ','.join(data)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.