Ask Question
4 May, 02:43

The Sieve of Eratosthenes is an elegant algorithm for finding all the prime numbers up to some limit n. The basic idea is to first create a list of numbers from 2 to n. The first number is removed from the list, and announced as prime, and all multiples of this number is removed up to n are removed from the list. This process continues until the list is empty.

For example, if you wanted to find all the prime numbers up to 10, the list would contain 2, 3, 4, 5, 6, 7, 8, 9, 10. The 2 is removed and announced to be prime and 4, 6, 8, and 10 are removed since they are multiples of 2. That leaves 3, 5, 7, 9., repeat the process until the list is empty.

Write a program that prompts a user for n and then uses the sieve algorithm to find all the prime numbers less than or equal to n.

+1
Answers (1)
  1. 4 May, 05:51
    0
    Check the explanation

    Explanation:

    #! usr/bin/python

    #FileName: sieve_once_again. py

    #Python Version: 2.6.2

    #Author: Rahul Raj

    #Sat May 15 11:41:21 2010 IST

    fi=0 #flag index for scaling with big numbers ...

    n=input ('Prime Number (>2) Upto:')

    s=range (3, n, 2)

    def next_non_zero ():

    "To find the first non zero element of the list s"

    global fi, s

    while True:

    if s[fi]:return s[fi]

    fi+=1

    def sieve ():

    primelist=[2]

    limit = (s[-1]-3) / 2

    largest=s[-1]

    while True:

    m=next_non_zero ()

    fi=s. index (m)

    if m**2>largest:

    primelist+=[prime for prime in s if prime] #appending rest of the non zero numbers

    break

    ind = (m * (m-1) / 2) + s. index (m)

    primelist. append (m)

    while ind<=limit:

    s[ind]=0

    ind+=m

    s[s. index (m) ]=0

    #print primelist

    print 'Number of Primes upto %d: %d'% (n, len (primelist))

    if __name__=='__main__':

    sieve ()
Know the Answer?
Not Sure About the Answer?
Find an answer to your question ✅ “The Sieve of Eratosthenes is an elegant algorithm for finding all the prime numbers up to some limit n. The basic idea is to first create a ...” in 📘 Computers and Technology if you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers