Crivo de Atkin

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.

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+1, 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())