{"id":25771,"date":"2017-10-25T20:28:16","date_gmt":"2017-10-25T14:58:16","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25771"},"modified":"2017-10-25T20:28:16","modified_gmt":"2017-10-25T14:58:16","slug":"python-programming-sieve-eratosthenes","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-sieve-eratosthenes\/","title":{"rendered":"Python programming – Sieve of Eratosthenes"},"content":{"rendered":"

Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
\nFor example, if n is 10, the output should be \u201c2, 3, 5, 7\u201d. If n is 20, the output should be \u201c2, 3, 5, 7, 11, 13, 17, 19\u201d.<\/p>\n

The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million<\/p>\n

\n

Following is the algorithm to find all the prime numbers less than or equal to a given integer\u00a0n<\/em>\u00a0by Eratosthenes\u2019 method:<\/p>\n

    \n
  1. Create a list of consecutive integers from 2 to\u00a0n<\/em>: (2, 3, 4, \u2026,\u00a0n<\/em>).<\/li>\n
  2. Initially, let\u00a0p<\/em>\u00a0equal 2, the first prime number.<\/li>\n
  3. Starting from\u00a0p<\/em>, count up in increments of\u00a0p<\/em>\u00a0and mark each of these numbers greater than\u00a0p<\/em>\u00a0itself in the list. These numbers will be 2p<\/em>, 3p<\/em>, 4p<\/em>, etc.; note that some of them may have already been marked.<\/li>\n
  4. Find the first number greater than\u00a0p<\/em>\u00a0in the list that is not marked. If there was no such number, stop. Otherwise, let\u00a0p<\/em>\u00a0now equal this number (which is the next prime), and repeat from step 3.<\/li>\n<\/ol>\n

    When the algorithm terminates, all the numbers in the list that are not marked are prime.<\/p>\n[ad type=”banner”]\n<\/div>\n

    Explanation with Example:<\/strong>
    \nLet us take an example when n = 50. So we need to print all print numbers smaller than or equal to 50.<\/p>\n

    We create a list of all numbers from 2 to 50<\/p>\n

    According to the algorithm we will mark all the numbers which are divisible by 2.<\/p>\n

    \"\"<\/p>\n

    Now we move to our next unmarked number 3 and mark all the numbers which are multiples of 3.<\/p>\n

    \"\"<\/p>\n

    We move to our next unmarked number 5 and mark all multiples of 5.<\/p>\n

    \"\"<\/p>\n

    We continue this process and our final table will look like below:<\/p>\n

    \"\"<\/p>\n

    So the prime numbers are the unmarked ones: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.<\/p>\n[ad type=”banner”]\n

    Implementation:<\/strong>
    \nFollowing is C++ implementation of the above algorithm. In the following implementation, a boolean array arr[] of size n is used to mark multiples of prime numbers.<\/p>\n

    Python Program<\/span> <\/div> 
    # Python program to print all primes smaller than or equal to# n using Sieve of Eratosthenes def SieveOfEratosthenes(n):         # Create a boolean array "prime[0..n]" and initialize    #  all entries it as true. A value in prime[i] will    # finally be false if i is Not a prime, else true.    prime = [True for i in range(n+1)]    p=2    while(p * p <= n):                 # If prime[p] is not changed, then it is a prime        if (prime[p] == True):                         # Update all multiples of p            for i in range(p * 2, n+1, p):                prime[i] = False        p+=1    lis =[]         # Print all prime numbers    for p in range(2, n):        if prime[p]:            print p, # driver programif __name__=='__main__':    n = 30    print "Following are the prime numbers smaller",    print "than or equal to", n    SieveOfEratosthenes(n)<\/code><\/pre> <\/div>\n
    Output:<\/strong><\/p>\n
    Following are the prime numbers below 30\r\n2 3 5 7 11 13 17 19 23 29<\/pre>\n","protected":false},"excerpt":{"rendered":"
    Python programming – Sieve of Eratosthenes – Mathematical Algorithms – Given a number n, print all primes smaller than or equal to n.For example, if n.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,74058,4148],"tags":[75194,75318,75196,75218,75210,75231,75313,75206,75306,75298,75326,75320,75323,75312,75322,75200,75302,75300,72110,74978,75303,75301,75299,75308,75310,75295,75314,75311,75324,75297,75309,75325,75321,75294,75304,75229,75208,75317,75216,75319,75226,75222,75315,75228,75316,75230,75307,75327,75305,75296],"class_list":["post-25771","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-mathematical-algorithms","category-python","tag-algorithm-for-finding-prime-numbers","tag-algorithm-for-prime-number","tag-algorithm-to-find-prime-numbers","tag-define-sieve-of-eratosthenes","tag-eratosthenes-method","tag-eratosthenes-sieve-java","tag-eratosthenes-sieve-method","tag-how-to-find-prime-numbers","tag-linked-list-in-python-tutorial","tag-list-of-prime-numbers","tag-list-of-prime-numbers-to-10000","tag-list-of-primes","tag-list-prime-numbers","tag-prime-factorization-in-python","tag-prime-generator","tag-prime-number-algorithm","tag-prime-number-checker-python","tag-prime-number-in-python","tag-prime-number-program-in-c","tag-prime-number-program-in-python","tag-prime-number-program-python","tag-prime-number-python-code","tag-prime-numbers-list","tag-prime-sieve","tag-primes-less-than-1000","tag-primes-python","tag-program-for-prime-number-in-python","tag-python-code-to-find-prime-numbers","tag-python-function-tutorial","tag-python-lambda-function-list-comprehension","tag-python-lambda-tutorial","tag-python-prime-number-generator","tag-python-program-for-prime-number","tag-python-program-to-check-prime-number","tag-python-program-to-find-prime-numbers","tag-sieve-c","tag-sieve-method-to-find-prime-numbers","tag-sieve-method-to-find-prime-numbers-in-c","tag-sieve-number","tag-sieve-of-eratosthenes-algorithm","tag-sieve-of-eratosthenes-algorithm-in-c","tag-sieve-prime","tag-sieve-wiki","tag-sieving-method","tag-singly-linked-list-in-python","tag-the-sieve","tag-what-is-sieve-number","tag-what-is-sieve-of-eratosthenes","tag-what-is-the-sieve-of-eratosthenes","tag-write-a-python-program-to-find-prime-numbers"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25771","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25771"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25771\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25771"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25771"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25771"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}