test_primes2.py

# Cfr. https://forum.ubuntu-it.org/viewtopic.php?p=5297724#p5297724
# ... and https://forum.ubuntu-it.org/viewtopic.php?f=33&t=649359
# ... and https://gist.github.com/crap0101/7dd3acd6f294507505fc23a5b62890ef

import argparse
import functools
import itertools
import collections
import math
import operator
import sys
import time
import timeit


def is_primo(n):
    #by nuzzopippo
    lst_range = [x for x in range(2, n+1)]
    lim = int(math.sqrt(n))
    pivot = 2
    while pivot <= lim:
        for i in range(len(lst_range)):
            if lst_range[i]:
                if lst_range[i] != pivot and lst_range[i] % pivot == 0:
                    lst_range[i] = 0
        pivot += 1
    primes = [x for x in lst_range if x != 0]
    #if n in primes:
    #    return True
    #return False
    return primes

def prime_sieve(n):
    #based on is_primo__refact3
    #Sieve of Eratosthenes, modified
    if n < 3 and n != 2:
        return []
    elif n == 2:
        return [2]
    lst = list(x for x in range(3, n+1, 2))
    lst.insert(0, 2)
    lim = int(math.sqrt(n))
    pivot = 1
    m = lst[pivot]
    while m <= lim:
        for i in range(pivot+1, len(lst)):
            x = lst[i]
            if x and not x % m:
                lst[i] = 0
        pivot += 1
        m = lst[pivot]
        lst = list(i for i in lst if i)
    return lst

def prime_sieve2(n):
    #Sieve of Eratosthenes, modified
    if n < 2:
        return []
    up = n+1
    lst = list(x for x in range(up))
    lst[1] = 0
    lim = int(math.sqrt(n))
    pivot = 2
    while lst[pivot] <= lim:
        for i in range(pivot+pivot, up, pivot):
            lst[i] = 0
        for p in range(pivot+1, up):
            if lst[p] != 0:
                pivot = p
                break
    return list(x for x in lst if x)

def prime_sieve3(n):
    # Euler's sieve, a kind of...
    if n < 2:
        return []
    up = n + 1
    lst = list([x, 1] for x in range(up))
    lst[0][1] = lst[1][1] = 0
    lim = int(math.sqrt(n))
    pivot = 2
    m = lst[pivot][0]
    while m <= lim:
        for i in range(pivot, up):
            try:
                lst[m*lst[i][0]][1] = 0
            except IndexError:
                break
        for p in range(pivot+1, up):
            if lst[p][1] != 0:
                pivot = p
                break
        m = lst[pivot][0]
    return list(x for x,mark in lst if mark)


def prime_sieve3w(n): ########XXXXXTODOOOOOO
    # wheeeeeeel...
    raise NotImplementedError("to be written... :-D")
    if n < 2:
        return []
    basis = [2,3,5]
    p = product(basis)
    wheel = []
    for i in range(6, p+1):
        if all(gcd(i, n) for n in basis):
            wheel.append(i)

    
def is_primo_elementary(n):
    #by nuzzopippo, modified
    if n < 2:
        return False
    for d in range(2, int(math.sqrt(n)) + 1):
        if n % d == 0:
            return False
    return True

def is_prime(x):
    if x < 2 or (x!=2 and not x%2):
        return False
    elif x in (2, 3, 5, 7):
        return True
    a = 3
    limite = math.sqrt(x)
    while a <= limite:
        if not (x % a):
            return False
        a += 2
    return True

def is_prime__mod(x):
    if x < 2:
        return False
    elif x in (2, 3, 5, 7):
        return True
    for n in (2, 3, 5, 7):
        if not x % n:
            return False
    limite = int(math.sqrt(x))
    for a in range(11, limite+1, 2):
        if not x % a:
            return False
    return True

def is_prime__mod2(x):
    if x < 2:
        return False
    elif x in (2, 3, 5, 7):
        return True
    for n in (2, 3, 5, 7):
        if not x % n:
            return False
    return all(x%a for a in range(11, int(x**.5)+1, 2))


def is_prime_wiki(n: int) -> bool:
    """https://en.wikipedia.org/wiki/Primality_test
    Primality test using 6k+-1 optimization."""
    if n <= 3:
        return n > 1
    if not n%2 or not n%3:
        return False
    i = 5
    stop = int(n**0.5)
    while i <= stop:
        if not n%i or not n%(i + 2):
            return False
        i += 6
    return True

def is_prime_wiki__mod(n: int) -> bool:
    """https://en.wikipedia.org/wiki/Primality_test
    Primality test using 6k+-1 optimization."""
    b = (2,3,5)
    if n in b:
        return True
    if n < 2 or any(n%x==0 for x in b):
        return False
    i = 5
    stop = int(n**0.5)+1
    for i in range(5, stop, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True


#################
# utility funcs #
#################

def gcd(x, y): # math.gcd !!!:-D
    """Return the greatest common divisor of *x* and *y*."""
    if y == 0:
        return x
    r = x % y
    while r:
        x, y = y, r
        r = x % y
    return y

def product (numbers):
    """
    Returns the product of the elements in `numbers' or 1 if empty
    https://en.wikipedia.org/wiki/Empty_set#Operations_on_the_empty_set
    """
    it = iter(numbers)
    try:
        tot = next(it)
    except StopIteration:
        return 1
    for i in it:
        tot *= i
    return tot

def product_ (numbers):
    """
    Returns the product of the elements in `numbers' or 1 if empty
    https://en.wikipedia.org/wiki/Empty_set#Operations_on_the_empty_set
    """
    try:
        return functools.reduce(operator.mul, numbers)
    except TypeError:
        return 1

########################
# others utility funcs #
########################

def _fake (f, arg):
    return f(arg)

def _check_prime (f, arg): # for sieves
    return arg in f(arg)

def _check_primes_list (f, arg): # for prime check
    return list(i for i in range(arg+1) if f(i))


##############
# test times #
##############

def verify_time_is_prime(funcs, n):
    print('Tempi per verificare se %d è primo:' % n)
    report = 'Funzione {:<20} | risultato {} | tempo: {:.10f}'
    for f, wrap in funcs:
        start = time.time()
        result = wrap(f, n)
        end = time.time()
        print(report.format(f.__name__, result, end - start))

def verify_time_primes_list(funcs, n):
    print('Tempi per verificare i numeri primi fino a %d:' % n)
    report = 'Funzione {:<20} || tempo: {:.10f}'
    for f, wrap in funcs:
        start = time.time()
        wrap(f, n)
        end = time.time()
        print(report.format(f.__name__,  end - start))

#############
# test: cmp #
#############

def _test_compare (funcs, data, ttype):
    _ttype = ('numbers', 'nrange')
    if ttype not in _ttype:
        raise ValueError("'ttype' must be one of %s".format(_ttype))
    elif ttype == _ttype[0]:
        _dtypef = ('({},..,{})'.format(data[0], data[-1])
                   if len(data) > 1
                   else '({})'.format(data[0]))
    else:
        _dtypef = '[0..{}]'.format(max(data))
    print("Test compare ({}|{}): ".format(ttype, _dtypef), end='')
    sys.stdout.flush() # bha!
    for (f1, w1), (f2, w2) in itertools.combinations(funcs, 2):
        if ttype == _ttype[0]:
            for i in data:
                assert w1(f1, i) == w2(f2, i), "({}) | {} <> {}".format(
                    i, f1.__name__, f2.__name__)
        elif ttype == _ttype[1]:
            for i in range(max(data)): 
                assert w1(f1, i) == w2(f2, i), "({}) | {} <> {}".format(
                    i, f1.__name__, f2.__name__)
    print('OK')


###################
# some more tests #
###################

def _test_ufuncs():
    print('Test funcs for __eq__:', end=' ')
    for i in range(int(time.time() % 1000)):
        assert product(list(range(i))) == product_(range(i))
        j = int(time.time() % 100)
        assert gcd(i, j) == math.gcd(i, j)
    print('OK')
    print('Test for speed...')
    # --- product*
    n = 10
    funcs = 'product product_'.split()
    setup = 'from __main__ import {}'.format(','.join(funcs))
    stmt = 'for i in range(10, 10000): {}(range(i))'
    report = 'function {:<10}|{:.5}s'
    for f in funcs:
        t = timeit.Timer(stmt=stmt.format(f), setup=setup).timeit(number=n)
        print(report.format(f, t / n))
    # --- gcd*
    n = 100
    __m, __n = int(time.time() % 10), - int(time.time() % 100)
    setup = 'from __main__ import gcd, math, time'
    stmt = 'for a, b in zip(range(10, int(10e5), __m), range(int(10e7), 10, __n)):{}(a, b)'
    for f in 'gcd math.gcd'.split():
        t = timeit.Timer(stmt=stmt.format(f), setup=setup, globals=locals()).timeit(number=n)
        print(report.format(f, t / n))


###################
# cmdline parsing #
###################

def get_parsed (funclist):
    p = argparse.ArgumentParser()
    p.add_argument('-f', '--funcs',
                   dest='flist', choices=funclist, nargs='+',
                   default=funclist, metavar='funcname',
                   help='funcs to run (default: all). Choices from: %(default)s')
    p.add_argument('-n','--numbers', dest='numbers',
                   default=(63977, 779591, 1007683), type=int, nargs='+', metavar='N',
                   help='run test choice (-p, -s, or both) with this numbers')
    p.add_argument('-p','--prime', dest='check_is_prime', action='store_true',
                   help='run check (or test, with -t) for single primes (passed with -n)')
    p.add_argument('-s','--sieve-list', dest='check_prime_list', action='store_true',
                   help='run check (or test, with -t) for generation of primes up to numbers passed with -n')
    p.add_argument('-t','--test', dest='test', action='store_true',
                   help='run test for specified -p or -s options.')
    p.add_argument('-T','--more-test', dest='test_more', action='store_true',
                   help='test on some others utility functions')
    return p.parse_args()


    
if __name__ == '__main__':
    # list of [function, wrapper for single prime test, wrapper for prime list generation]
    _funcs_wrap = [(is_primo_elementary, _fake, _check_primes_list),
                   (is_prime, _fake, _check_primes_list),
                   (is_prime__mod, _fake, _check_primes_list),
                   (is_prime__mod2, _fake, _check_primes_list),
                   (is_prime_wiki, _fake, _check_primes_list),
                   (is_prime_wiki__mod, _fake, _check_primes_list),
                   #(is_primo, _check_prime, _fake), # tooooo slow
                   (prime_sieve, _check_prime, _fake),
                   (prime_sieve2, _check_prime, _fake),
                   (prime_sieve3, _check_prime, _fake),
                   #(prime_sieve3w, _check_prime, _fake),
    ]
    _flist = [f[0].__name__ for f in _funcs_wrap]
    funcs_wrap_p = []
    funcs_wrap_plist = []
    args = get_parsed(_flist)
    for fname in args.flist:
        for f, wp, wl in _funcs_wrap:
            if f.__name__ == fname:
                if args.check_is_prime:
                    funcs_wrap_p.append((f, wp))
                if args.check_prime_list:
                    funcs_wrap_plist.append((f, wl))
                break
    if args.test:
        if args.check_is_prime:
            _test_compare(funcs_wrap_p, args.numbers, 'numbers')
        if args.check_prime_list:
            _test_compare(funcs_wrap_plist, args.numbers, 'nrange')
    if args.test_more:
        _test_ufuncs()
    if (args.test or args.test_more):
        sys.exit(0)
    if args.check_is_prime:
        for n in args.numbers:
            verify_time_is_prime(funcs_wrap_p, n)
    if args.check_prime_list:
            for n in args.numbers:
                verify_time_primes_list(funcs_wrap_plist, n)

"""
crap0101@orange:~/test$ python3 test_primes2.py -f  is_prime is_prime__mod  is_prime_wiki  -ps
Tempi per verificare se 63977 è primo:
Funzione is_prime             | risultato True | tempo: 0.0000257492
Funzione is_prime__mod        | risultato True | tempo: 0.0000131130
Funzione is_prime_wiki        | risultato True | tempo: 0.0000290871
Tempi per verificare se 779591 è primo:
Funzione is_prime             | risultato True | tempo: 0.0000774860
Funzione is_prime__mod        | risultato True | tempo: 0.0000422001
Funzione is_prime_wiki        | risultato True | tempo: 0.0000438690
Tempi per verificare se 1007683 è primo:
Funzione is_prime             | risultato True | tempo: 0.0000896454
Funzione is_prime__mod        | risultato True | tempo: 0.0000472069
Funzione is_prime_wiki        | risultato True | tempo: 0.0000495911
Tempi per verificare i numeri primi fino a 63977:
Funzione is_prime             || tempo: 0.1354715824
Funzione is_prime__mod        || tempo: 0.0866899490
Funzione is_prime_wiki        || tempo: 0.0751483440
Tempi per verificare i numeri primi fino a 779591:
Funzione is_prime             || tempo: 4.2491497993
Funzione is_prime__mod        || tempo: 2.3829643726
Funzione is_prime_wiki        || tempo: 2.1068589687
Tempi per verificare i numeri primi fino a 1007683:
Funzione is_prime             || tempo: 5.9754381180
Funzione is_prime__mod        || tempo: 3.3913729191
Funzione is_prime_wiki        || tempo: 3.0249435902

crap0101@orange:~/test$ python3 test_primes2.py -f  is_prime is_prime__mod  is_prime_wiki  -pstT -n 999
Test compare (numbers|(999)): OK
Test compare (nrange|[0..999]): OK
Test funcs for __eq__: OK
Test for speed...
function product   |3.7849s
function product_  |2.709s
function gcd       |0.2056s
function math.gcd  |0.051126s

"""