Crivo de Atkin: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Correção de indentação no código |
|||
Linha 23: | Linha 23: | ||
try: |
try: |
||
if self.sieve[prime]: |
if self.sieve[prime]: |
||
self.sieve[prime] = False |
self.sieve[prime] = False |
||
except KeyError: |
except KeyError: |
||
pass |
pass |
Revisão das 11h54min de 5 de maio de 2016
Crivo de Atkin é um algoritmo matemático moderno usado para encontrar todos os números primos até determinado valor máximo. Ele é uma versão aprimorada do Crivo de Eratóstenes e com um desempenho assintótico melhor. Foi criado em 2003 por Arthur Oliver Lonsdale Atkin e Daniel J. Bernstein.[1]
Implementação
#Implementação em python do Crivo de Atkin
from math import sqrt, ceil, pow
class SieveOfAtkin:
def __init__(self, limit):
self.limit = limit
self.primes = []
self.sieve = [False]*(self.limit+1)
def flip(self, prime):
try:
self.sieve[prime] = not self.sieve[prime]
except KeyError:
pass
def invalidate(self, prime):
try:
if self.sieve[prime]:
self.sieve[prime] = False
except KeyError:
pass
def isPrime(self, prime):
try:
return self.sieve[prime]
except KeyError:
return False
def getPrimes(self):
testingLimit = int(ceil(sqrt(self.limit)))
for i in range(testingLimit):
for j in range(testingLimit):
# n = 4*i^2 + j^2
n = 4*int(pow(i, 2)) + int(pow(j,2))
if n <= self.limit and (n % 12 == 1 or n % 12 == 5):
self.flip(n)
# n = 3*i^2 + j^2
n = 3*int(pow(i, 2)) + int(pow(j,2))
if n <= self.limit and n % 12 == 7:
self.flip(n)
# n = 3*i^2 - j^2
n = 3*int(pow(i, 2)) - int(pow(j,2))
if n <= self.limit and i > j and n % 12 == 11:
self.flip(n)
for i in range(5, testingLimit):
if self.isPrime(i):
k = int(pow(i, 2))
for j in range(k, self.limit, k):
self.invalidate(j)
self.primes = [2, 3] + [x for x in range(len(self.sieve)) if self.isPrime(x) and x>=5]
return self.primes
soa = SieveOfAtkin(1000000)
print soa.getPrimes()
Referências
- ↑ A.O.L. Atkin, D.J. Bernstein, Crivos de números primos usando formas quadráticas binárias (Prime sieves using binary quadratic forms), Math. Comp. 73 (2004), 1023-1030.[1]