Algorithms in C++: Programming Assignment 1 Solution

    1. Objective

Your goal is to write a program to find prime numbers using the sieve of Eratosthenes.

    2. Problem

You are to create a C++ project called sieve, a C++ source file called sieve.cpp, and class inside it called PrimesSieve that finds prime numbers. The program asks the user for a limit, and then finds primes up to and including that limit. When there is only one line of prime numbers in the output, the numbers should be displayed with one space between each (and no space at the end). When there are multiple lines of output, the numbers should be right-aligned to the width of the largest prime. See below.

**************************** Sieve of Eratosthenes **************************** Search for primes up to: <user enters 20>

Number of primes found: 8
Primes up to 20:
235711131719

**************************** Sieve of Eratosthenes **************************** Search for primes up to: <user enters 200>

Number of primes
found:
46













Primes up to 200:
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
2
3
5
7
















            73 79  83  89  97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173

            179 181 191 193 197 199

    3. Tips

        a. Use the template file found in Canvas. The framework for the program is there, and you will need to fill in the methods.

        b. If a function/method is inline, the compiler places a copy of the code of that function/method at each point where it is called at compile time. inline is used for efficiency with short (one-line) functions/methods.

        c. Look up setw in the iomanip library to set the width of a field that is to be outputted.

        d. #include <cmath> for the sqrt function.

        e. You may have up to 80 characters on a line. If you cannot fit all the primes on one line, you should wrap around to the next line. To find the width of the maximum prime value

and how many primes you can fit on a row, use the following code:
const int max_prime_width = num _digits(max_prime _), primes_per_row = 80 / (max_prime_width + 1);

Before printing each prime, determine how many spaces are needed to right-align the number, and set the field width accordingly.

f.    Be sure to comment your code and put your name and Stevens pledge at the top.Make sure your code works with the test.sh autograder shell script.

    g. The algorithm for the sieve is found in pseudocode below.

************************ Sieve of Eratosthenes ************************ Input: an integer n > 1

Let is_prime be an array of bool values, indexed by integers 2 to n, initially all set to true.
for i = 2, 3, 4, ..., while i ≤ √ :

if is_prime[i] is true:
for j = i2, i2  + i, i2  + 2i, ..., while j ≤ n:

is_prime[j] = false

Now all i such that is_prime[i] is true are prime.