Python Program- In this problem we revisit the Sieve of Eratosthenes. Since we k
ID: 3590339 • Letter: P
Question
Python Program-
In this problem we revisit the Sieve of Eratosthenes. Since we know that 2 is the only even prime, it is wasteful of memory to include information for even numbers. Instead our array should start with the information for 3 and then only keep track of the information for the odd numbers (3, 5, 7, 9, . . .).
The program should list the primes less that or equal to an input number, call it n. We may as well assume n is odd. Hints: Note that 2i + 3 runs through the odd numbers in question for i = 0, 1, 2, 3, . . . . We can use slot i in our array to store the information for the odd number 2i + 3. Write a function that takes i and returns 2i + 3. Write the inverse function also.
These functions should enable you to easily find the right places in the array and the corresponding numbers. Give some sample output of a value of n that’s pretty big, but the output will fit on one page. What is the biggest value of n you can process in less than or equal to one minute?
Explanation / Answer
from array import *
def inputfunction():
return ((2 * i) + 3)
def reverse():
if (n%2) == 0:
return ((n-4)/2)
else:
return ((n-3)/2)
def printprime():
for k in range(0,num+1):
#print(num)
for j in range(2,odd[k]):
if (odd[k] % j) == 0:
break
else:
print(odd[k])
odd = array("l");
n = input("Enter a number : ")
num=reverse()
for i in range(0,num+1):
odd.append(inputfunction())
printprime()
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.