"""
Implementation of the "Sieve of Eratosthenes"
algorithm.
It aims at finding all primes that are less
than or equal to a certain upperbound,
denoted by n.
Time complexity: O(n log log n)
Space complexity: O(n)
"""
import math
def findPrimes(n):
# Only 1 prime <= 2
if n <= 2:
return [2]
"""
Initialize numbers[0] and numbers[1] as False
because 0 and 1 are not prime.
Set numbers[2] through numbers[n-1] to True
When we find a divisor for one of them, set
it to False
"""
numbers = [False, False] + [True] * (n - 1)
sqrtN = int(math.sqrt(n))
for p in range(2, sqrtN + 1):
if numbers[p]:
# Set all multiples of p to false
# because they are not prime.
for multiple in range(p * p, n+1, p):
numbers[multiple] = False
# put all primes in a list
result = []
for p in range(n+1):
if numbers[p]:
result.append(p)
return result
print(findPrimes(13)) # [2, 3, 5, 7, 11, 13]
print(findPrimes(19)) # [2, 3, 5, 7, 11, 13, 17, 19]