
"""
Andrew Kavas
Prime Sieve of Atkin

"""

# Generates list of prime numbers LESS than n in value
# Uses Atkin polynomial: (x-1)**p - (x**p-1)
# if all coefficients are divisible by p, then p is prime
# Faster poly: (x-a)**p - (x**p-a)
# where a is determined by p
# Faster than Eratosthenes past n = 10 billion

import math

def sieveOfAtkin(limit):
    
    P = [2,3]
    sieve=[False]*(limit+1)
    for x in range(1,int(math.sqrt(limit))+1):
        for y in range(1,int(math.sqrt(limit))+1):
            n = 4*x**2 + y**2
            if n<=limit and (n%12==1 or n%12==5) : sieve[n] = not sieve[n]
            n = 3*x**2+y**2
            if n<= limit and n%12==7 : sieve[n] = not sieve[n]
            n = 3*x**2 - y**2
            if x>y and n<=limit and n%12==11 : sieve[n] = not sieve[n]
    for x in range(5,int(math.sqrt(limit))):
        if sieve[x]:
            for y in range(x**2,limit+1,x**2):
                sieve[y] = False
    for p in range(5,limit):
        if sieve[p] : P.append(p)
    return P

#print(sieveOfAtkin(1000000))

