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

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()

Step-by-step 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.