prime starting numbers

Updated TrustyTony 1 Tallied Votes 271 Views Share

Finding efficiently primes, whose begining numbers are also primes. See the thread http://www.daniweb.com/software-development/cpp/threads/425821/prime-number-c in C++ forum for discussion on topic.

import pretty # http://www.daniweb.com/software-development/python/code/345935/printing-things-nicely-pretty-printer-revisited
from functools import update_wrapper
import time

def is_prime_(n):
    if n in (2, 3):
        return True
    elif n < 2 or not n % 2 or not n % 3:
        return False

    if n < 9:
        return True
    r = int(n ** 0.5)
    f = 5
    while f <= r:
        if not n % f or not n % (f + 2):
            return False
        f += 6
    return True

def timestr(t):
    return ( ("%i min %.3f s" % divmod(t, 60)) if t > 60
            else  (("%.3f s" % t) if t > 1
                   else ("%.3f ms" % (t * 1000)) if t > 0.001 else ("%i us" % (t*10**6))
                   )
            )

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

    return update_wrapper(wrapper, func)
 

@timing
def special_primes(length = 8):
    primes = [n for n in range(1,10) if is_prime(n)]
    all_fit = [primes[:]]
    for n in range(length-1):
        #print('%i: %2i solutions: %s\n' % (n+1, len(primes), primes))
        newprimes = [p * 10 + a for p in primes for a in 1,3,7,9 if is_prime(p * 10 + a)]
        if not newprimes:
            #print n+2, 'and longer impossible'
            break
        all_fit.append(newprimes)
        primes = newprimes
    return all_fit

if __name__ == '__main__':
    s = special_primes()
    print('\nLengths and counts:')
    pretty.printer(list((ind, len(v)) for ind, v in enumerate(s, 1)))

    print('Total solutions count: %i' % sum(map(len, s)))
    print('\nThe numbers by lengths:')
    pretty.printer(s)

""" Output:
special_primes took 9.128 ms

Lengths and counts:

  [
    (1, 4), 
    (2, 9), 
    (3, 14), 
    (4, 16), 
    (5, 15), 
    (6, 12), 
    (7, 8), 
    (8, 5)]
Total solutions count: 83

The numbers by lengths:

  [
    [2, 3, 5, 7], 
    [23, 29, 31, 37, 53, 59, 71, 73, 79], 
    [233, 239, 293, 311, 313, 317, 373, 379, 593, 599, 719, 733, 739, 797], 
    [2333, 2339, 2393, 2399, 2939, 3119, 3137, 3733, 3739, 3793, 3797, 5939, 7193, 7331, 7333, 7393], 
    [23333, 23339, 23399, 23993, 29399, 31193, 31379, 37337, 37339, 37397, 59393, 59399, 71933, 73331, 73939], 
    [233993, 239933, 293999, 373379, 373393, 593933, 593993, 719333, 739391, 739393, 739397, 739399], 
    [2339933, 2399333, 2939999, 3733799, 5939333, 7393913, 7393931, 7393933], 
    [23399339, 29399999, 37337999, 59393339, 73939133]]
"""