Question

Python Program

Eratosthenes of Cyrene lived approximately 275-195 BC. He was the first to accurately estimate the diameter of the earth. For several decades he served as the director and chief librarian of the famous library in Alexandria. He was highly regarded in the ancient world, but unfortunately only fragments of his writing have survived.

The algorithm described for this assignment is known as the Sieve of Eratosthenes. The algorithm is designed to find all prime numbers within a given range in an interesting way - instead of testing each number to see if it is prime, it assumes that all numbers are prime. It then finds all "non-prime" numbers and marks them as such. When the algorithm is finished you are left with a list of numbers along with their designation (Prime or Not Prime). Here's a detailed outline of how the algorithm works:

• We will examine a range of numbers starting at 0 and going up to a number entered by the user, and determine which numbers in this range are prime. Your lowest number will be 0 and your highest number will be n.
  
• Create a list of n+1 values where n is the highest number you want to test. Populate each element in this list with the String "P" for "Prime" since we initially will assume that all numbers in our range are prime. For example, if you were testing all numbers between 0 and 10 your list would look like the following:

  0	1	2	3	4	5	6	7	8	9	10
  P	P	P	P	P	P	P	P	P	P	P

• Next, we need to indicate that our "special case" numbers - 0 and 1 - are not prime. To do this simply switch the values of elements 0 and 1 to "N" for "Not Prime". Your list should look like this:

  0	1	2	3	4	5	6	7	8	9	10
  N	N	P	P	P	P	P	P	P	P	P

• Next, we we will move onto our first "non-special" number, 2. The value at position 2 in the list is currently "P" meaning that 2 is a prime number. Our job now is to mark every MULTIPLE of 2 equal to "N" for "Not Prime" since any number evenly divisible by 2 cannot possibly be prime. So we can set up some kind of looping structure to visit all multiples of 2 and set them equal to "N" for "Not Prime". Your list should look like this after this operation:

  0	1	2	3	4	5	6	7	8	9	10
  N	N	P	P	N	P	N	P	N	P	N

• Now we move onto our next number, 3. The value at position 3 in the list is listed as "P" meaning we need to mark all multiples of 3 equal to "N" for "Not Prime". Note that the number 6 was already visited in a previous iteration of your program so there's really nothing to do here - it was already marked as "Not Prime" so you can safely move onto the next number and not make any changes to it. Your list should look like this after this operation:

  0	1	2	3	4	5	6	7	8	9	10
  N	N	P	P	N	P	N	P	N	N	N

• Next we move onto the number 4. 4 is marked as "Not Prime", so there is nothing to do here. We can skip it and move right onto the next number to test.
  
• The value at position 5 in the list is listed as "P" meaning we need to mark all multiples of 5 equal to "N" for "Not Prime". Your list should look like this after this operation:

  0	1	2	3	4	5	6	7	8	9	10
  N	N	P	P	N	P	N	P	N	N	N

• Next we move onto the number 6. But really, there's no need to even examine this number since all of its multiples are beyond the end of our maximum range (6 * 2 > 10). So we can effectively stop the program at this point and examine all numbers in our list. Any number that has been marked with a "P" is a Prime number!

Here is your task:

• Ask the user for a positive integer greater than or equal to 10. Ensure the value is positive - if it isn't, re-prompt the user. This number will be referred to as n.
• Create a list of n+1 values ... all of which are set to "P" (hint: use list repetition). This list represents the numbers 0 to n (based on the indexes in the list)
• Set your "known" non-prime numbers (positions 0 and 1) to "N" for "Not Prime"
• Set up some kind of loop that examines all numbers from 2 through n.
  • If the value stored at the position you are examining is holding the value "P" for "Prime" then you need to visit all positions that are multiples of that number and set the value at those positions equal to "N" for "Not Prime". You will probably need another loop to do this.
  • If the value stored at the position you are examining is holding the value "N" for "Not Prime" then you can effectively skip it and move onto the next number.
• When you are finished examining all numbers your program should print out all of the prime numbers that you have found in neatly aligned columns (with up to 10 prime numbers on every row). Sample output:

  2       3       5       7      11      13      17      19      23      29     
 31      37      41      43      47      53      59      61      67      71     
 73      79      83      89      97     101     103     107     109     113     
127     131     137     139     149     151     157     163     167     173     
179     181     191     193     197     199     211     223     227     229     
233     239     241     251     257     263     269     271     277     281     
283     293     307     311     313     317     331     337     347     349     
353     359     367     373     379     383     389     397     401     409     
419     421     431     433     439     443     449     457     461     463     
467     479     487     491     499     503     509     521     523     541     
547     557     563     569     571     577     587     593     599     601     
607     613     617     619     631     641     643     647     653     659     
661     673     677     683     691     701     709     719     727     733     
739     743     751     757     761     769     773     787     797     809     
811     821     823     827     829     839     853     857     859     863     
877     881     883     887     907     911     919     929     937     941     
947     953     967     971     977     983     991     997     
Found 168 prime numbers!

Notes on Efficiency:

Efficiency is important here - here are some hints:

• If an item in your list has already been set to "N" what does this tell you about the multiples of that item's index? Do you even need to visit them?
• Certain numbers don't need to be tested. Say you are testing all numbers between 0 and 1000 and you get to the number 800. This number cannot have any multiples less than or equal to 1000. Generalize this idea to make your program much more efficient.

For more information about this algorithm (and an animated representation of it running) check out the wikipedia article: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 1

Explanation::

• Code in PYTHON is given below
• Ouputis provided at the end

Code in PYTHON::

import math

'''

Declaring the variable named n to store the value entered by user

'''

n=0

'''

Following while loop ask user to enter value until

valid input is not entered

'''

while True:

  n=int(input("Enter the value of n : "))

  if(n>=10):

    break

  print("Invalid number! At least 10.")

'''

Now we create a list named number[]

and initialize it to hold 'P' for n+1 elements

'''

number = []

for i in range(n+1):

  number.insert(i,'P')

'''

Initialize first two number elements as 'N'

'''

number[0]='N'

number[1]='N'

'''

Now we mark all the even numbers are 'N' except 2

'''

for i in range(4,n+1,2):

  number[i]='N'

'''

An crosslimit is declared below which will be used to

stop processing ahead numbers like if n=1000 then no need

to check multiple of 800

'''

crosslimit=int(math.sqrt(n))

for i in range(3,crosslimit+1,2):

  if number[i]=='P':

    for j in range(i*i,n+1,2*i):

      number[j]='N'

'''

Now we print the numbers that are prime

'''

j=int(1)

for i in range(len(number)):

  if number[i]=='P':

    if j%10==0:

      j=1

      print('{:<5}'.format(i))

    else:

      j=j+1

      print('{:<5}'.format(i),end="")

print()

OUTPUT::

Enter the value of n : 9

Invalid number! At least 10.

Enter the value of n : 1000

2 3 5 7 11 13 17 19 23 29

31 37 41 43 47 53 59 61 67 71

73 79 83 89 97 101 103 107 109 113

127 131 137 139 149 151 157 163 167 173

179 181 191 193 197 199 211 223 227 229

233 239 241 251 257 263 269 271 277 281

283 293 307 311 313 317 331 337 347 349

353 359 367 373 379 383 389 397 401 409

419 421 431 433 439 443 449 457 461 463

467 479 487 491 499 503 509 521 523 541

547 557 563 569 571 577 587 593 599 601

607 613 617 619 631 641 643 647 653 659

661 673 677 683 691 701 709 719 727 733

739 743 751 757 761 769 773 787 797 809

811 821 823 827 829 839 853 857 859 863

877 881 883 887 907 911 919 929 937 941

947 953 967 971 977 983 991 997

Please provide the feedback!!

Thank You!!