Strumenti Utente

Strumenti Sito


sieveatkin

Il crivello di Atkin è un algoritmo per trovare tutti i numeri primi fino ad un dato valore intero.

Una rozza implementazione utilizzando Python:

from math import sqrt, ceil
 
# numero di valori da considerare
nTot = 1000000
 
# calcola solo per numeri inferiori alla radice del valore totale
root = int(sqrt(nTot))
nums = []
primes = [2, 3]
 
# valore di primalita' di default (falso)
for tmp in range(0, nTot):
    nums.append(False)
 
for x in range(1, root):
    for y in range(1, root):
        # crivello di Atkin
        n = 4*x*x + y*y
        if n <= nTot and (n % 12 == 1 or n % 12 == 5):
            nums[n] = True
        n = 3*x*x + y*y
        if n <= nTot and n % 12 == 7:
            nums[n] = True
        n = 3*x*x - y*y
        if x > y and n <= nTot and n % 12 == 11:
            nums[n] = True
 
# i quadrati non sono primi
for r in range(5, root):
    if nums[r]:
        for i in range(r*r, nTot, r*r):
            nums[i] = False
 
# estrae i primi
for a in range(5, nTot):
    if nums[a]:
        primes.append(a)
 
print 'found ' + str(len(primes)) + ' primes:'
print primes
sieveatkin.txt · Ultima modifica: 2017/05/03 15:48 (modifica esterna)