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 thats 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?