Pure Programmer
Blue Matrix

Cluster Map

Project: Sieve of Eratosthenes

A simple way to find prime numbers is to use the [[Sieve of Eratosthenes]]. We start by creating an array of booleans initialized to true. Then we set to false elements that have indexes that are multiples of 2, 3, 5, 7, etc. We will end up with an array that only has elements that are true when their index is a prime number.

Write a program that uses a Sieve of Eratosthenes to compute then print all the prime numbers less than 1000. The program should also print the number of primes found. How large can you make the sieve array before you run out of memory?

$ g++ -std=c++17 SieveOfEratosthenes.cpp -o SieveOfEratosthenes -lfmt $ ./SieveOfEratosthenes 2 3 5 7 11 13 17 19 23 29 ... 947 953 967 971 977 983 991 997 168 primes found.