This I did also after 'spying' discussions in other forum. Of course you would use sieve prime generation for bigger numbers, but I proved other simple way for a change.

Slightly more advanced primes list generator would use primes % 6 in (1,5) property:

``````def primes(n):
""" primitive non-sieve prime finder """
p = [2, 3]
candidate, step = 5, 2
while candidate <= n:
if all(candidate % pr for pr in p):
p.append(candidate)
candidate += step
# consider only number % 6 in (1,5) ie 6*n +- 1
step = 2 if step == 4 else 4

return p``````
141 Views
``````def primes(n):
""" primitive non-sieve prime finder """
p = 
for i in range(3,n+1,2):
if all(i % pr for pr in p):
p.append(i)
return p

def possible_sums(seq, limit):
return set(a+b for ind, a in enumerate(seq) for b in seq[ind:] if a+b <= limit)

def test_sum(limit=10000):
# 4 is only with sum of two even primes == 2 + 2, testing from 6 until limit
print('''
Testing that even numbers from 6 until %i are expressable by
not necessary different pair of odd primes
(4 = 2 + 2 is only even case)...
''' % limit)
not_ok = set(range(6, limit, 2)) - (possible_sums(primes(limit)[1:], limit))
print('Test passed' if not not_ok else 'No prime sum for '+str(not_ok))

if __name__ == '__main__':
test_sum()``````

IT Pro doing Eng-Fin-Eng translations

For drastic speedup for the primes generator, use itertools.takewhile and stop at sqrt of candidate:

``````import itertools
from utils import timing

@timing
def primes(n):
""" primitive non-sieve prime finder """
p = [2, 3]
candidate, step = 5, 2
while candidate <= n:
if all(candidate % pr for pr in itertools.takewhile(lambda x: x * x <= candidate, p)):
p.append(candidate)
candidate += step
# consider only number % 6 in (1,5) ie 6*n +- 1
step = 2 if step == 4 else 4

return p

print(len(primes(10**5)))``````

Timing before and after:

``````primes took 15.643 s
9592
primes took 632 ms
9592``````

The timing decoreator in utils.py

``````import time
def timing(func):
def wrapper(*arg):
t1 = time.clock()
res = func(*arg)
t2 = time.clock()
print('%s took %s' % (func.__name__, timestr(t2-t1)))
return res
wrapper.__doc__, wrapper.__name__, wrapper.__module__ = func.__doc__, func.__name__, func.__module__
return wrapper``````

Does not compare so well still with fastest numpy based sieve:

``````Primes upto 1000000
primes took 11.997 s
78498
fastprimes took 172.043 ms
78498
>>>``````