3·The well known sieve of Eratosthenes is very effetive for finding nil the prim

Question

3·The well known sieve of Eratosthenes is very effetive for finding nil the prime numbers less than or equal to an integer n. Here is a general algorithm for it from some secret suthor Step 1. Create a list of consecutive integers from 2 to n: (2, 3, 4,..., D). Step 2. Initially, let p equal 2, the first prime number. Step 3. Starting from p, count up in increments of p and mark ench of these numbers than p itself in the list. These numbers will be 2p, 3p, 4p, ete.; may have alrendy been marked. note that some of them Step 4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3. When the algorithm terminates, all the numbers in the list that are not marked are prime. A portion of an implementation of this algorithm is presented below. The goal is to complete this implementation as indicated by the questions that follow this code. 1 void sieve0fEratosthenes(Vector &1sPrime) 2 3 4 5 6 7 Vector crossedout (n, false) for (int p = 0; p

Explanation / Answer

(a)
n should be the total number of integers in the input vector.
Therefore line 2 is the following:

int n = isPrime.size()

So, we have a vector of size n with n integers starting from 0.
For integers < 2, isPrime[p] is initialized to false.

Completed algorithm:

void sieveOfEratosthenes(Vector<bool> & isPrime) {
   int n = isPrime.size()
   Vector<bool> crossedOut(n, false);
   for (int p = 0; p < n; p++) {
       if (p< 2) {
           isPrime[p] = false;
       }
       else {
           if (isPrime[p] != false) // it is not already crossed out
           for (i = p; i < n; i++)
           {
               if (i%p == 0) {
                   isPrime[i] = false;
               }

           }
       }
   }
}

b)
The primary data structure used is isPrime

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.