Reference the algorithm in the attched image. (a) Write code to implement the algorithm in python. (b) Show the output for Sieve(60) and Sieve(200) (c) Modify the code to count the number of times the if statement on line 3 is executed. (d) Show the output for Sieve (160) including the output for part (c) above
Reference the
(a) Write code to implement the algorithm in python.
(b) Show the output for Sieve(60) and Sieve(200)
(c) Modify the code to count the number of times the if statement on line 3 is executed.
(d) Show the output for Sieve (160) including the output for part (c) above
![ALGORITHM Sieve(n)
//Implements the sieve of Eratosthenes
//Input: A positive integer n > 1
//Output: Array L of all prime numbers less than or equal to n
for p 2 to n do A[p] + p
for p +2 to √√ndo
if A[p] #0
j← p*p
while j≤ n do
A[j] 0 //mark element as eliminated
j+j+p
//copy the remaining elements of A to array L of the primes
i←0
for p +2 to n do
if A[p] #0
//see note before pseudocode
//p hasn't been eliminated on previous passes
L[i] + A[p]
i←i +1
return L](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F16a501d0-ad86-4e86-a9d4-08a716d78319%2F9fdb781a-1eeb-44f0-8bae-63728952b7e7%2Fs7mmm4l_processed.png&w=3840&q=75)
Algorithm:
-
Initialize a count variable to 0 and create a list of n+1 elements with all elements set to True, where n is the input value.
-
Loop through the range of 2 to the square root of n+1.
-
For each iteration of the loop, check if the current value of the list is True. If it is, increment the count variable by 1 and perform the following steps.
-
Initialize a variable j as the square of the current iteration number.
-
While j is less than or equal to n, set the corresponding element in the list to False and increment j by the current iteration number.
-
After the loop, initialize an empty list L.
-
Loop through the range of 2 to n+1.
-
For each iteration of the loop, check if the current value of the list is True. If it is, append the current iteration number to the list L.
-
Return the list L and the count variable as the output of the function.
-
Call the function with input values 60, 200, 50, and 160 and print the output.
Step by step
Solved in 6 steps with 7 images
