Skip to content

Instantly share code, notes, and snippets.

@gerlacdt
Created September 21, 2021 18:25
Show Gist options
  • Save gerlacdt/772c86b2f592a16ea6303defaf74974f to your computer and use it in GitHub Desktop.
Save gerlacdt/772c86b2f592a16ea6303defaf74974f to your computer and use it in GitHub Desktop.
# Program collects all primes less than or equal n.
# It uses the Sieve of Eratosthenes algorithm, see
# https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
def primes(n):
# Initializes start array with n-entries, all numbers are primes initially
prime = [True for i in range(n + 1)]
# 0 and 1 are no primes
prime[0] = False
prime[1] = False
# start from 2 as first prime
p = 2
while p * p <= n:
# number not crossed out yet, it must be a prime
if prime[p] == True:
# Cross out all multiples of p
for i in range(p ** 2, n + 1, p):
prime[i] = False
p += 1
# collect all primes, the numbers not crossed out
return [i for i, v in enumerate(prime) if v]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment