test_primes.py

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

import math
import time

def is_primo(n):
    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

def is_primo__refact(n):
    if n < 5:
        return True if n in (2, 3) else False
    lst = list(range(3, n+1, 2))
    _len = len(lst)
    lim = int(math.sqrt(n))
    pivot = 0
    m = lst[pivot]
    while m <= lim:
        m = lst[pivot]
        if m:
            for i in range(pivot+1, _len):
                x = lst[i]
                if x and not x % m:
                    lst[i] = 0
        pivot += 1
    return n in lst

def is_primo__refact2(n):
    if n < 5:
        return True if n in (2, 3) else False
    elif not n % 2:
        return False
    lst = list(range(3, n+1, 2))
    lim = int(math.sqrt(n))
    pivot = 0
    m = lst[pivot]
    while m <= lim:
        lst = list(i for i in lst if i)
        m = lst[pivot]
        for i in range(pivot+1, len(lst)):
            x = lst[i]
            if x and not x % m:
                lst[i] = 0
        pivot += 1
    return n in lst

def is_primo__refact3(n):
    if n <= 5:
        return True if n in (2, 3, 5) else False
    elif not n % 2:
        return False
    lst = list(x for x in range(3, n+1, 2) if x % 5)
    lim = int(math.sqrt(n))
    pivot = 0
    m = lst[pivot]
    while m <= lim:
        lst = list(i for i in lst if i)
        m = lst[pivot]
        for i in range(pivot+1, len(lst)):
            x = lst[i]
            if x and not x % m:
                lst[i] = 0
        pivot += 1
    return lst[-1] == n

def is_primo__refact4(n):
    if n < 5:
        return True if n in (2, 3) else False
    elif not n % 2:
        return False
    up = n+1
    lst = bytearray(1 for _ in range(up))
    lst[0] = lst[1] = 0
    for i in range(4, up, 2):
        lst[i] = 0
    lim = int(math.sqrt(n))
    pivot = 3
    while pivot <= lim:
        for i in range(pivot+1, up):
            if not i % pivot:
                lst[i] = 0
        pivot += 2
    return bool(lst[n])

def is_primo__refact5(n):
    if n <= 5:
        return True if n in (2, 3, 5) else False
    elif not n % 2:
        return False
    up = n + 1
    a = 0
    #a |= (1 << 0); a |= (1 << 1) # ignore this
    #for i in range(4, up, 2): a |= (1 << i) # ... and this
    lim = int(math.sqrt(n))
    pivot = 3
    while pivot <= lim:
        for i in range(pivot+1, up):
            if not i % pivot:
                a |= (1 << i)
        pivot += 2
    return not bool((a >> n) & 1)

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_primo_elementary(n):
    for d in range(2, int(math.sqrt(n)) + 1):
        if n % d == 0:
            return False
    return True

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 verify_time(n):
    print('Test tempi per verificare se %d è primo:' % n)
    funcs = (is_primo_elementary, is_prime, is_prime_wiki,
             is_primo, is_primo__refact, is_primo__refact2,
             is_primo__refact3, is_primo__refact4,
             is_primo__refact5)
    report = 'Funzione {:<20} | risultato {} | tempo: {:.10f}'
    for f in funcs:
        start = time.time()
        result = f(n)
        end = time.time()
        tempo = '{:.10f}'.format(end - start)
        print(report.format(f.__name__, result, end - start))



if __name__ == '__main__':
    #for i in range(3999): assert is_prime(i)  == is_primo__refact5(i), "ERR: %d" % i
    #for i in range(14): print(i, is_primo__refact4(i))
    #__import__("sys").exit(1)
    for n in (63977, 779591, 1007683):
        verify_time(n)


"""
crap0101@orange:~/test$ python3 test_primes.py 
Test tempi per verificare se 63977 è primo:
Funzione is_primo_elementary  | risultato True | tempo: 0.0000345707
Funzione is_prime             | risultato True | tempo: 0.0000224113
Funzione is_prime_wiki        | risultato True | tempo: 0.0000281334
Funzione is_primo             | risultato True | tempo: 1.6902666092
Funzione is_primo__refact     | risultato True | tempo: 0.1850836277
Funzione is_primo__refact2    | risultato True | tempo: 0.1232452393
Funzione is_primo__refact3    | risultato True | tempo: 0.1153991222
Funzione is_primo__refact4    | risultato True | tempo: 0.7133312225
Funzione is_primo__refact5    | risultato True | tempo: 1.2470622063
Test tempi per verificare se 779591 è primo:
Funzione is_primo_elementary  | risultato True | tempo: 0.0001022816
Funzione is_prime             | risultato True | tempo: 0.0000741482
Funzione is_prime_wiki        | risultato True | tempo: 0.0000445843
Funzione is_primo             | risultato True | tempo: 69.5928032398
Funzione is_primo__refact     | risultato True | tempo: 5.8784887791
Funzione is_primo__refact2    | risultato True | tempo: 3.5701422691
Funzione is_primo__refact3    | risultato True | tempo: 3.2892744541
Funzione is_primo__refact4    | risultato True | tempo: 33.1914861202
Funzione is_primo__refact5    | risultato True | tempo: 129.2330808640
Test tempi per verificare se 1007683 è primo:
Funzione is_primo_elementary  | risultato True | tempo: 0.0001215935
Funzione is_prime             | risultato True | tempo: 0.0000848770
Funzione is_prime_wiki        | risultato True | tempo: 0.0000495911
Funzione is_primo             | risultato True | tempo: 100.3405344486
Funzione is_primo__refact     | risultato True | tempo: 8.3384702206
Funzione is_primo__refact2    | risultato True | tempo: 4.8012452126
Funzione is_primo__refact3    | risultato True | tempo: 4.5025062561
Funzione is_primo__refact4    | risultato True | tempo: 48.8617985249
Funzione is_primo__refact5    | risultato True | tempo: 211.9745793343
"""