Question: I need help written in python. Question 6 (40 points). The Sieve of Eratosthenes is an algorithm for discovering all prime numbers up to certain
Question 6 (40 points). The Sieve of Eratosthenes is an algorithm for discovering all prime numbers up to certain maximum number, max num. This is accomplished by "marking off all multiples of prime numbk to the max num. Composite numbers are removed from the list by setting them to zero. Once you off all multiples up to the square root of max num, the remaining (non-zero) numbers in your list are all pn Write a function named eratosthenes () that takes an integer, indicating the maximum number, as a parameter and implements the following algorithm: prime numbers up to a 1. Generate a list L of all numbers between 2 and max num (inclusive). 2. Iterate through this list one element at a time: a. If the element is less than 2, this element (and its multiples) have already been marked off as not b. If the number is greater than the square root of max num, there is no need to continue prime, so continue with the loop without marking off any multiples of this element. numbers, so exit the loop. Set all the multiples of this element (not including itself) up to (and including) max num, to 3. Return a list of all non-zero elements. These are all primes up to max_num! be 0 Example: Suppose max num = 26 Initial list L=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 Mark off multiples of 2 (not including 2) by setting them to 0 L= 2 3 5 7 9 11 13 15 17 19 21 23 25 Mark off multiples of 3 (not including 3) by setting them to 0 L= 2 3 0 5 7 0 0 11 13 0 0 17 19 We don't need to check 4, because it's already 0, so we proceed to 5: Mark off multiples of 5 (not including 5) by setting them to 0 0 0 23 25 0 0 L-2 3 0 50 7 00 11 013 0 017 019 0 0 23 0 0 Thus, the prime numbers under 26 are 2, 3, 5, 7, 11, 13, 17, 19, 23 RETURN this list at the end of your function. Your solution MUST follow the algorithm above
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
