Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import math
- def sieveOfAtkin(numberToNotExceed):
- listOfPrimes = [2, 3, 5]
- sieve = [False] * (numberToNotExceed + 1)
- integerRootOfNumberToNotExceed = int(math.sqrt(numberToNotExceed)) + 1
- for x in range(1, integerRootOfNumberToNotExceed):
- for y in range(1, integerRootOfNumberToNotExceed):
- entryNumber = 4 * x ** 2 + y ** 2 ### n = 4x^2 + y^2
- if (entryNumber <= numberToNotExceed) and (entryNumber % 12 == 1 or entryNumber % 12 == 5):
- sieve[entryNumber] = not sieve[entryNumber]
- entryNumber = 3 * x ** 2 + y ** 2 ### n = 3x^2 + y^2
- if (entryNumber <= numberToNotExceed) and (entryNumber % 12 == 7):
- sieve[entryNumber] = not sieve[entryNumber]
- if x > y:
- entryNumber = 3 * x ** 2 - y ** 2 ### n = 3x^2 - y^2
- if (entryNumber <= numberToNotExceed) and (entryNumber % 12 == 11):
- sieve[entryNumber] = not sieve[entryNumber]
- for index in range(5, integerRootOfNumberToNotExceed):
- if sieve[index]:
- for composite in range(index ** 2, numberToNotExceed, index ** 2):
- sieve[composite] = False
- for index in range(7, numberToNotExceed):
- if sieve[index]:
- listOfPrimes.append(index)
- return listOfPrimes
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement