{"id":25770,"date":"2017-10-25T20:25:22","date_gmt":"2017-10-25T14:55:22","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25770"},"modified":"2017-10-25T20:25:22","modified_gmt":"2017-10-25T14:55:22","slug":"java-programming-sieve-eratosthenes","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-sieve-eratosthenes\/","title":{"rendered":"Java 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

    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=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20to%20print%20all%20primes%20smaller%20than%20or%20equal%20to%0A%2F%2F%20n%20using%20Sieve%20of%20Eratosthenes%0A%20%0Aclass%20SieveOfEratosthenes%0A%7B%0A%20%20%20%20void%20sieveOfEratosthenes(int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20a%20boolean%20array%20%22prime%5B0..n%5D%22%20and%20initialize%0A%20%20%20%20%20%20%20%20%2F%2F%20all%20entries%20it%20as%20true.%20A%20value%20in%20prime%5Bi%5D%20will%0A%20%20%20%20%20%20%20%20%2F%2F%20finally%20be%20false%20if%20i%20is%20Not%20a%20prime%2C%20else%20true.%0A%20%20%20%20%20%20%20%20boolean%20prime%5B%5D%20%3D%20new%20boolean%5Bn%2B1%5D%3B%0A%20%20%20%20%20%20%20%20for(int%20i%3D0%3Bi%3Cn%3Bi%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20prime%5Bi%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20for(int%20p%20%3D%202%3B%20p*p%20%3C%3Dn%3B%20p%2B%2B)%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%20If%20prime%5Bp%5D%20is%20not%20changed%2C%20then%20it%20is%20a%20prime%0A%20%20%20%20%20%20%20%20%20%20%20%20if(prime%5Bp%5D%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%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%20%20%20%20%20for(int%20i%20%3D%20p*2%3B%20i%20%3C%3D%20n%3B%20i%20%2B%3D%20p)%0A%20%20%20%20%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%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Print%20all%20prime%20numbers%0A%20%20%20%20%20%20%20%20for(int%20i%20%3D%202%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if(prime%5Bi%5D%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(i%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F%2F%20Driver%20Program%20to%20test%20above%20function%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%2030%3B%0A%20%20%20%20%20%20%20%20System.out.print(%22Following%20are%20the%20prime%20numbers%20%22)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22smaller%20than%20or%20equal%20to%20%22%20%2B%20n)%3B%0A%20%20%20%20%20%20%20%20SieveOfEratosthenes%20g%20%3D%20new%20SieveOfEratosthenes()%3B%0A%20%20%20%20%20%20%20%20g.sieveOfEratosthenes(n)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJava 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
    \u00a0<\/p>\n
    \u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"
    Java programming – Sieve of Eratosthenes – Mathematical Algorithms – Given a number n, print all primes smaller than or equal to n.For example, if n is 10.<\/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,2139,74058],"tags":[75194,75259,75196,75197,72484,72358,75232,75214,75250,75203,75218,75262,75260,75210,75256,75241,75237,75206,75244,75261,75233,75234,75238,75245,75246,75239,75255,75258,75209,75251,75243,75236,75200,75252,75247,72110,75240,75254,75235,72106,75248,75253,75242,75208,75216,75226,75222,75257,75249],"class_list":["post-25770","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-java","category-mathematical-algorithms","tag-algorithm-for-finding-prime-numbers","tag-algorithm-for-java-program","tag-algorithm-to-find-prime-numbers","tag-algorithm-to-find-prime-numbers-from-1-to-n","tag-algorithms-in-java","tag-c-program-to-find-prime-number","tag-check-for-prime-number-java","tag-check-prime-number","tag-check-prime-number-in-java","tag-cprime","tag-define-sieve-of-eratosthenes","tag-doubly-linked-list-code-java","tag-doubly-linked-list-java-tutorial","tag-eratosthenes-method","tag-eratosthenes-of-cyrene","tag-finding-a-prime-number-in-java","tag-how-to-check-if-a-number-is-prime-in-java","tag-how-to-find-prime-numbers","tag-java-code-for-prime-number-checking","tag-java-code-to-find-prime-numbers","tag-java-number","tag-java-program-algorithm-examples","tag-java-program-for-prime-number","tag-java-program-of-prime-number","tag-java-program-prime-number","tag-java-program-to-find-prime-number","tag-linked-list-java-code-example","tag-prime-generator-java","tag-prime-no-in-c","tag-prime-no-in-java","tag-prime-no-program","tag-prime-no-program-in-java","tag-prime-number-algorithm","tag-prime-number-checker","tag-prime-number-in-java","tag-prime-number-program-in-c","tag-prime-number-program-in-java","tag-prime-numbers-from-1-to-100-in-java","tag-prime-numbers-java-code","tag-program-for-prime-number-in-java","tag-program-of-prime-no-in-java","tag-program-to-check-prime-number","tag-program-to-check-prime-number-in-java","tag-sieve-method-to-find-prime-numbers","tag-sieve-number","tag-sieve-of-eratosthenes-algorithm-in-c","tag-sieve-prime","tag-simple-prime-no-program-in-java","tag-write-a-java-program-to-check-prime-number"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25770","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=25770"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25770\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25770"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25770"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25770"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}