Question

4.3 Ch 4 Ex 14 - sieve of Erotosthenes

In this lab, you will write a program to compute all the prime numbers between 2 and some other integer, using an algorithm called the Sieve of Erotosthenes.

First you will read, from standard input, the integer that will be the upper limit of the range of primes. Call it max.

Then, create a vector<int> with max elements, and call it is_composite. The result of the Sieve will be that is_composite[i] will be 1 if i is composite, and 0 if it is prime.

We'll ignore entries 0 and 1; we really don't care about them. Here is pseudocode for the Sieve algorithm:

    for every integer i from 2 to max
        if i is not composite
            for every multiple of i up to max
                mark that multiple as composite

The numbers for which is_composite[i] remains 0 are prime numbers.

For example, say max is 30. We start out with is_composite looking like this:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

The first time through outer the loop, we see that 2 is prime, so we set all its multiples (4, 6, 8, …, 28) to 1 to mark them as composite.is_composite now looks like this:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
0	0	0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0

The next time through the outer loop, we see that 3 is also prime, so we mark its multiples (6, 9, 12, …, 27) as composite:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
0	0	0	0	1	0	1	0	1	1	1	0	1	0	1	1	1	0	1	0	1	1	1	0	1	0	1	1	1	0

Next, we see that 4 is composite, so we don't need to mark its multiples. This makes sense, since all multiples of 4 are also multiples of 2, and we've already marked those as composite.

We then see that 5 is prime, and so we mark all its multiples (10, 15, 20, 25) as composite:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
0	0	0	0	1	0	1	0	1	1	1	0	1	0	1	1	1	0	1	0	1	1	1	0	1	1	1	1	1	0

When we're done, we'll see that the elements of is_composite that are still 0 - 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29 - are all prime.

Write out the primes on a single line, with a space after each one. End the output with a newline. For example, if the input is 30, the output should be:

2 3 5 7 11 13 17 19 23 29 

Here are some hints concerning a couple of optional optimizations you can make:

1. The outer loop does not have to run all the way to max. The next hint may help you figure out what the limit of the outer loop could be.
2. When marking multiples, you don't have to start at i * 2; you can actually start at a higher value. Hint: You may find the sqrt()function useful; if so, you need to include the <cmath> header.

Notes:

All the elements of a vector<int> are automatically initialized to 0.

It may seem that using a vector<bool> would make more sense. Unfortunately, due to a well-intentioned but ultimately faulty attempt at treating vector<bool> as an optimized special case, its use is not recommended.

LAB

Answer 1

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int main() {
int max;
cin>>max;
vector<int> is_composite(max + 1);

for(int i=2;i<=sqrt(max);i++){
if(!is_composite[i]){
for(int j=i*2;j<=max;j = j += i){
is_composite[j] = 1;
}
}
}

for(int i=2;i<=max;i++){
if(!is_composite[i])
cout<<i<<" ";
}
cout<<endl;
return 0;
}