Strumenti Utente

Strumenti Sito


sieveatkin

Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

Link a questa pagina di confronto

sieveatkin [2017/05/03 15:48] (versione attuale)
Linea 1: Linea 1:
 +Il crivello di //Atkin// è un algoritmo per trovare tutti i numeri primi fino ad un dato valore intero.
 +
 +Una rozza implementazione utilizzando Python:
 +
 +<code 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
 +</​code>​
  
sieveatkin.txt · Ultima modifica: 2017/05/03 15:48 (modifica esterna)