Skip to the content of the web site.

Project H.1.d: Sieve of Eratosthenes

For this project, you will have to additionally know how to implement an array class and how to dynamically allocate such a class.

Your array class must:

  • Have a public member function std::size_t Array::capacity() const that returns the array capacity.
  • Have a public member function T operator[]( std::size_t k ) that returns the $k$th entry of the array.

Write a function with the declaration

Array *prime_list( unsigned long n );

which dynamically allocates a unsigned long array with a capacity equal to the number of primes less than or equal to $n$ with the entries of that data structure containing the prime numbers.

You can test your code with

#include <iostream>
#include "Array.h"

// Function and data structure declarations
Array<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 ) {
		Array *primes{ prime_list( k ) };

		std::cout << (*primes)[0];

		for ( unsigned long j{1}; j < primes->capacity(); ++j ) {
			std::cout << ", " << (*primes)[j];
		}

		std::cout << std::endl;

		delete primes;
		primes = nullptr;
	}

	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