1.11M Members

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

 
0
 

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()
Member Avatar
Tony Veijalainen

Specialties:
IT/Science/Contracts/Religious translation/interpreting FIN-ENG-FIN
Python programming

 
0
 

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
>>>
Isn't it about time forums rewarded their contributors?

Earn rewards points for helping others. Gain kudos. Cash out. Get better answers yourself.

It's as simple as contributing editorial or replying to discussions labeled or OP Kudos

You
This is an OP Kudos discussion and contributors may be rewarded
Post:
Start New Discussion
View similar articles that have also been tagged: