Continuare la Formula calcul numere prime.
Se pare ca Python 3 in varianta mai noua foloseste calcule cu numere intregi in precizie arbitrara (precizie infinita) adica stocarea numerelor nu e limitata la 32-64-128 biti.
Am reusit in Python sa cresc un pic numarul de numere prime generate.
Functia originala este prime1(), iar functia imbunatatita de mine este prime2():
#!/bin/env python3
#
# https://www.youtube.com/watch?v=j5s0h42GfvM
#
import math
import time
import sys
from functools import cache
@cache
def factorial(n):
return 1 if n <= 1 else n * factorial(n-1)
def prime1(n):
return 1 + sum([
math.floor(pow(n/sum([
math.floor(pow(math.cos(math.pi * (math.factorial(j - 1) + 1)/j), 2))
for j in range(1, i+1)
]), 1/n))
for i in range(1, pow(2, n)+1)
])
def prime2(n):
sum1 = 0
for i in range(1, 1+pow(2, n)):
if i % 100:
print(f'Test {i} \r', end='')
#sys.stdout.flush()
sum2 = 0
for j in range(1, i+1):
f = factorial(j - 1) + 1
# f = math.factorial(j - 1) + 1
if (f // j) * j == f:
sum2 += 1
v = pow(n/sum2, 1/n)
if v>=1:
sum1 += 1
return 1 + sum1
def main():
print('Calcul 1')
n = 1
while True:
start = time.time()
try:
v = prime1(n)
except Exception as e:
print(e)
break
end = time.time()
print(f'Prime #{n} = {v} - {end-start:.2f} sec')
n += 1
print()
print('Calcul 2')
n = 1
while True:
start = time.time()
v = prime2(n)
end = time.time()
print(f'Prime #{n} = {v} - {end-start:.2f} sec')
n += 1
if __name__ == "__main__":
main()
Cu prime1() se determina primele 7 numere prime, iar functia are un bug (python are un bug) la rotunjirea facuta de math.floor().
Dar cu prime2() se obtin in cateva secunde primele 10 numere prime si lista e identica cu o alta lista gasita pe Internet, dar dupa acea nu apar erori, dar afisarea rezultatelor se face din ce in ce mai rar pentru ca numarul de calcule efectuate creste exponential si numerele prime sunt din ce in ce mai rare.
Functia prime2() afiseaza pe ecran ce pozitie testeaza, ultiumul numar prim afisat repede este 31, ca sa afiseze 37 (urmatorul numar prim) trebuie sa ajunga cu teste la pozitia 2 la puterea 12 (37 este al 12-lea numar prim) = 212 = 4096 si este tare, tare greu pentru python, iar pypy testat de mine nu merge ca nu are functools.
Nefolosind cache din functools si apeland math.factorial, merge si cu pypy, dar merge un pic mai repede decat Python, curios, pentru ca pypy accelereaza executia programelor Python de 2-20 de ori!
Python gaseste numarul 31 ca fiind prim in 30.6 secunde, iar pypy il gaseste in 21.1 secunde, apoi pypy gaseste pe 37 in 239.5 sec, …
Dar algoritmul este foarte lent, formula este impractica.
Un program simplu de cautare prime:
n = 1
start = time.time()
while True:
n += 1
if 0 == n % 2:
continue
flag = True
for i in range(3, n//2, 2):
if 0 == n % i:
flag = False
break
if flag:
end = time.time()
print(f'{n} - {end-start:.2f} sec')
if n > 1000:
break
gaseste lejer numerele prime sub 1000 in zero secunde, si sub 10000 in 0.04 secunde.