🍈 Zettelkasten

Sieve of Erathosthenes

1 min read

Prints all primes smaller or equal to a limit n Efficient of when n <= 10,000,000

Algorithm

  1. Assume all numbers from 2 to n are unmarked
  2. Mark the number 2 as prime, then mark all multiples of 2 as composite
  3. The next unmarked number from 2 is prime (3 in this case), then mark all multiples of 3 that are currently unmarked as composite
  4. Repeat the process with all subsequent unmarked numbers

Graph View