Skip to the content of the web site.

Project H.1.d: Sieve of Eratosthenes

For this project, you will re-implement Project d, but instead of returning a pointer to your Array class, you will return an instance of the std::vector class. Additionally, instead of using an array of type bool, which requires $N + 1$ bytes, you will use an instance of the std::vector<bool> class, which requires only one bit per entry or one-eighth the amount of memory.

Write a function with the declaration

std::vector<unsigned long> prime_list( unsigned long n );

which internally creates an instance of the std::vector<bool> class, and then once it has found the number of primes less than or equal to $n$, create an instance of the std::vector class, populate it with the prime numbers, and then return it. You will not need pointers.

You can test your code with

#include <iostream>
#include <bitset>
#include <vector>

// Function and data structure declarations
std::vector<unsigned long> prime_list( unsigned long n );
int main();

// Class definitions
// Your code here

// Function definitions
int main() {
	for ( unsigned long k{10}; k <= 80; k += 10 ) {
		auto primes = prime_list( k );

		auto itr = primes.begin();
		std::cout << *itr;
		++itr;

		for ( ; itr != primes.end(); ++itr ) {
			std::cout << ", " << *itr;
		}

		std::cout << std::endl;
	}

	return 0;
}

// Your code here;

The output should be

2, 3, 5, 7
2, 3, 5, 7, 11, 13, 17, 19
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79

References