Sample Input 0 10 Sample Output 0 Enter n: 10 [2, 3, 5, 7] Sample Input 1 50 Sample Output 1 Enter n: 50 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
How to apply this python code in the problem? What are the base cases and recursive cases that should be used?
def createList(n):
#Base Case/s
#TODO: Add conditions here for your base case/s
#if <condition> :
#return <value>
#Recursive Case/s
#TODO: Add conditions here for your recursive case/s
#else:
#return <operation and recursive call>
#remove the line after this once you've completed all the TODO for this function
return []
def removeMultiples(x, arr):
#Base Case/s
#TODO: Add conditions here for your base case/s
#if <condition> :
#return <value>
#Recursive Case/s
#TODO: Add conditions here for your recursive case/s
#else:
#return <operation and recursive call>
#remove the line after this once you've completed all the TODO for this function
return []
def Sieve_of_Eratosthenes(list):
#Base Case/s
if len(list) < 1 :
return list
#Recursive Case/s
else:
return [list[0]] + Sieve_of_Eratosthenes(removeMultiples(list[0], list[1:]))
if __name__ == "__main__":
n = int(input("Enter n: "))
print(n)
list = createList(n)
#Solution 1
primes = Sieve_of_Eratosthenes(list)
print(primes)
![Sample Input 0
10
Sample Output 0
Enter n: 10
[2, 3, 5, 7]
Sample Input 1
50
Sample Output 1
Enter n: 5o
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F5e4b46f5-fd0b-4b69-8fa1-4775c5e817f6%2F064f4b2f-b13f-4a1e-9d54-43c622d6f16b%2Ftlgxdae_processed.png&w=3840&q=75)
![You are to do a recursive implementation of the Sieve of Eratosthenes, an ancient algorithm
for finding all prime numbers up to a given limit, n, which we will let the user input.
We will be modifying this algorithm a bit. Instead of just marking the multiples of prime
numbers, we will directly remove them by creating our own helper
function, removeMultiples). This recursive function takes in a number, n, and a list and
returns a list that doesn't contain the multiples of n.
We will also create a recursive function, greateList), that takes in the user input n and returns an
array of integers from 2 through n (i.e. [2, 3, 4, ..., n]). You can use this list when testing
the removeMultiples() helper function above.
Our last recursive function is the SieveOfEratosthenes). This takes in a list and returns a list of
prime numbers from the input list. This function is already fully working in the given template to
make you focus more on implementing the first two. This is intended to serve as a guide on how to
create or manipulate arrays in a recursive manner.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F5e4b46f5-fd0b-4b69-8fa1-4775c5e817f6%2F064f4b2f-b13f-4a1e-9d54-43c622d6f16b%2F490y0j_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 2 images
