{"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=”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

    \"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=”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

    C Program<\/span> <\/div> 
    \/\/ C++ program to print all primes smaller than or equal to\/\/ n using Sieve of Eratosthenes#include <bits\/stdc++.h>using namespace std; void SieveOfEratosthenes(int 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.    bool prime[n+1];    memset(prime, true, sizeof(prime));     for (int p=2; p*p<=n; p++)    {        \/\/ If prime[p] is not changed, then it is a prime        if (prime[p] == true)        {            \/\/ Update all multiples of p            for (int i=p*2; i<=n; i += p)                prime[i] = false;        }    }     \/\/ Print all prime numbers    for (int p=2; p<=n; p++)       if (prime[p])          cout << p << " ";} \/\/ Driver Program to test above functionint main(){    int n = 30;    cout << "Following are the prime numbers smaller "         << " than or equal to " << n << endl;    SieveOfEratosthenes(n);    return 0;}<\/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[ad type=”banner”]\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}]}}