show all work and explanations 2. [20 points] Sieve of Eratosthenes (Ancient Greece, 200B.C.) Problem: A simple

show all work and explanations 

  

 

Transcribed Image Text:

2. [20 points] Sieve of Eratosthenes (Ancient Greece, 200B.C.) Problem: A simple algorithm for generating consecutive primes not exceeding any given integer n. Step 1: Initialize a list of prime candidates with consecutive integers from 2 to n. Step 2: Continue the step for eliminating from the list all multiples of 2, then 3, then 5, until no more numbers can be eliminated from the list. The remaining integers of the list are the primes needed. Questions: Given Algorithm Sieve(n) in our lecture note Ch 00_03_F IntroFoundation.pptx: 2.1 For the statement for p2 to n, do { ", state the reason for p going 2 to Vn.. 2.2 Given the following segment of statements in the Algorithm Sieve(n), for p 2 to n, do { if A[p] #0 { j p*p; while j n do { A[j] -0; j+j+p; }//end while_do } //end if p = p + 1; } //end for a. What is the purpose of " if A[p] #0 "? b. Given n = 1000, if p is 23 what are the number A[p], such that A[p] # 0, to be eliminated? 2. [20 points] Sieve of Eratosthenes (Ancient Greece, 200B.C.) Problem: A simple algorithm for generating consecutive primes not exceeding any given integer n. Step 1: Initialize a list of prime candidates with consecutive integers from 2 to n. Step 2: Continue the step for eliminating from the list all multiples of 2, then 3, then 5, until no more numbers can be eliminated from the list. The remaining integers of the list are the primes needed. Questions: Given Algorithm Sieve(n) in our lecture note Ch 00_03_F IntroFoundation.pptx: 2.1 For the statement for p2 to n, do { ", state the reason for p going 2 to Vn.. 2.2 Given the following segment of statements in the Algorithm Sieve(n), for p 2 to n, do { if A[p] #0 { j p*p; while j n do { A[j] -0; j+j+p; }//end while_do } //end if p = p + 1; } //end for a. What is the purpose of " if A[p] #0 "? b. Given n = 1000, if p is 23 what are the number A[p], such that A[p] # 0, to be eliminated?