Question

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method: 1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n), 2. Initially, let p equal 2, the first prime number, 3. While enumerating all multiples of p starting from p2, strike them off from the original list, 4. Find the first number remaining on the list after p (it's the next prime); let p equal this number, 5. Repeat steps 3 and 4 until p2 is greater than n. 6. All the remaining numbers in the list are prime.

Answer 1

Answer:

I am writing a Python program:

def Eratosthenes(n):  

   primeNo = [True for i in range(n+1)]  # this is a boolean array

   p = 2  # the first prime number is initialized as 2

   while (p * p <= n):     # enumerates all multiples of p

       if (primeNo[p] == True):                

           for i in range(p * p, n+1, p):  #update multiples

               primeNo[i] = False

       p = p + 1        

   for p in range(2, n):   #display all the prime numbers

       if primeNo[p]:  

           print(p),    

def main():     #to take value of n from user and display prime numbers #less than or equal to n by calling Eratosthenes method

   n= int(input("Enter an integer n: "))

   print("The prime numbers less than or equal to",n, "are: ")  

   Eratosthenes(n)      

main()      

Explanation:

The program contains a Boolean type array primeNo that is initialized by True which means that any value i in prime array will be true if i is a prime otherwise it will be false. The while loop keeps enumerating all multiples of p starting from 2, and striking them off from the original array list and for loops keep updating the multiples. This process will continue till the p is greater than n.  The last for loop displays all the prime numbers less than or equal to n which is input by user. main() function prompts user to enter the value of integer n and then calls Eratosthenes() function to print all the prime numbers less than or equal to a given integer n.