The Sieve of Eratosthenes works by generating a list of boolean values for each number less than our input, and setting them all to true. We then start at 2, and since it is marked as true, we know it is prime. We then mark off all numbers in our boolean set that are divisible by two as False, since any number divisible by a prime is obviously not prime. We then move to 3, and since it is marked as True, we know it is prime. We then mark off all multiples of 3, and repeat this process. We terminate the program when the square of a prime number is greater than our input value, and return our list of prime numbers. If we want a list of integers returned instead of an array of boolean values, we could just iterate through our list, appending the index of each cell still marked as true.
My code on GitHub can be found here if you want to check it out:
While it may not be the most interesting, the simplicity and efficiency of this algorithm compared to the naive approach makes it worth mentioning. Additionally, it dates back to roughly 276 B.C., which is just cool.
Thanks for reading!