{"id":25768,"date":"2017-10-25T20:22:45","date_gmt":"2017-10-25T14:52:45","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25768"},"modified":"2017-10-25T20:22:45","modified_gmt":"2017-10-25T14:52:45","slug":"c-programming-sieve-eratosthenes","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-sieve-eratosthenes\/","title":{"rendered":"C 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=\u201dbanner\u201d]\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

    \"sieve1\"<\/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=\u201dbanner\u201d]\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[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20print%20all%20primes%20smaller%20than%20or%20equal%20to%0A%2F%2F%20n%20using%20Sieve%20of%20Eratosthenes%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0Avoid%20SieveOfEratosthenes(int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20boolean%20array%20%22prime%5B0..n%5D%22%20and%20initialize%0A%20%20%20%20%2F%2F%20all%20entries%20it%20as%20true.%20A%20value%20in%20prime%5Bi%5D%20will%0A%20%20%20%20%2F%2F%20finally%20be%20false%20if%20i%20is%20Not%20a%20prime%2C%20else%20true.%0A%20%20%20%20bool%20prime%5Bn%2B1%5D%3B%0A%20%20%20%20memset(prime%2C%20true%2C%20sizeof(prime))%3B%0A%20%0A%20%20%20%20for%20(int%20p%3D2%3B%20p*p%3C%3Dn%3B%20p%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20prime%5Bp%5D%20is%20not%20changed%2C%20then%20it%20is%20a%20prime%0A%20%20%20%20%20%20%20%20if%20(prime%5Bp%5D%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Update%20all%20multiples%20of%20p%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20i%3Dp*2%3B%20i%3C%3Dn%3B%20i%20%2B%3D%20p)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prime%5Bi%5D%20%3D%20false%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Print%20all%20prime%20numbers%0A%20%20%20%20for%20(int%20p%3D2%3B%20p%3C%3Dn%3B%20p%2B%2B)%0A%20%20%20%20%20%20%20if%20(prime%5Bp%5D)%0A%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20p%20%3C%3C%20%22%20%22%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20Program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20n%20%3D%2030%3B%0A%20%20%20%20cout%20%3C%3C%20%22Following%20are%20the%20prime%20numbers%20smaller%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20%22%20than%20or%20equal%20to%20%22%20%3C%3C%20n%20%3C%3C%20endl%3B%0A%20%20%20%20SieveOfEratosthenes(n)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\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[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
    C programming – Sieve of Eratosthenes – Mathematical Algorithms – Given a number n, print all primes smaller than or equal to n. if n is 10, the output .<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69866,1,74058],"tags":[75218,75210,75231,75205,75206,75204,75221,75209,75192,75227,75200,75193,75195,72110,70565,75215,75223,74082,75212,75199,75229,75208,75216,75225,75226,75222,75228,72118,75217,75230],"class_list":["post-25768","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-mathematical-algorithms","tag-define-sieve-of-eratosthenes","tag-eratosthenes-method","tag-eratosthenes-sieve-java","tag-finding-prime-numbers","tag-how-to-find-prime-numbers","tag-n-prime","tag-number-4-sieve","tag-prime-no-in-c","tag-prime-no-program-in-c","tag-prime-no-program-in-c-language","tag-prime-number-algorithm","tag-prime-number-generation-program-in-c","tag-prime-number-program-in-c-language","tag-prime-number-program-in-c","tag-prime-numbers","tag-prime-numbers-from-1-to-100-in-c","tag-prime-series-in-c","tag-program-for-prime-number-in-c","tag-program-to-find-prime-numbers","tag-sieve","tag-sieve-c","tag-sieve-method-to-find-prime-numbers","tag-sieve-number","tag-sieve-number-4","tag-sieve-of-eratosthenes-algorithm-in-c","tag-sieve-prime","tag-sieving-method","tag-simple-c-program-for-prime-number","tag-simple-prime-number-program-in-c-language","tag-the-sieve"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25768","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=25768"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25768\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25768"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25768"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25768"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}