Skip to content

Instantly share code, notes, and snippets.

@crap0101
Last active May 4, 2022 22:31
Show Gist options
  • Save crap0101/7dd3acd6f294507505fc23a5b62890ef to your computer and use it in GitHub Desktop.
Save crap0101/7dd3acd6f294507505fc23a5b62890ef to your computer and use it in GitHub Desktop.
# 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
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment