Primitive test for expressivity of even number as sum of pair of prime (or double)

By Tony Veijalainen on May 15th, 2011 4:12 am

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

def primes(n):
    """ primitive non-sieve prime finder """
    p = [2] 
    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()

1 Year Ago

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
>>>

pyTony

pyMod

Moderator

5,359 posts since Apr 2010

Reputation Points: 782

Solved Threads: 852

This article has been dead for over three months

You