{"id":409,"date":"2020-02-13T17:06:18","date_gmt":"2020-02-13T17:06:18","guid":{"rendered":"https:\/\/www.samarthya.me\/wps\/?p=409"},"modified":"2020-02-13T17:06:18","modified_gmt":"2020-02-13T17:06:18","slug":"sieve-of-eratosthenes","status":"publish","type":"post","link":"https:\/\/blog.samarthya.me\/wps\/2020\/02\/13\/sieve-of-eratosthenes\/","title":{"rendered":"Sieve of Eratosthenes"},"content":{"rendered":"\n<p><a href=\"https:\/\/exercism.io\/my\/solutions\/28fecb68ecea4dcaa19d899dfa38a1e2\">Sieve<\/a> is an ancient and an ingenious way of calculating primes. It recursively eliminates all the multiples of a particular number up till a range and the left overs are essentially primes.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img fetchpriority=\"high\" decoding=\"async\" width=\"491\" height=\"399\" src=\"https:\/\/www.samarthya.me\/wps\/wp-content\/uploads\/2020\/02\/primes1.png\" alt=\"\" class=\"wp-image-412\" srcset=\"https:\/\/blog.samarthya.me\/wps\/wp-content\/uploads\/2020\/02\/primes1.png 491w, https:\/\/blog.samarthya.me\/wps\/wp-content\/uploads\/2020\/02\/primes1-300x244.png 300w\" sizes=\"(max-width: 491px) 100vw, 491px\" \/><figcaption>Computing primes up to 13<\/figcaption><\/figure><\/div>\n\n\n\n<p>It was just a matter of defining the right data structure and computing the final set of primes<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">package sieve\n\nimport \"sort\"\n\n\/\/ Sieve calculates prime\nfunc Sieve(limit int) (out []int) {\n    out = make([]int, 0)\n    myMap := make(map[int]bool, 0)\n\n    if limit &lt;= 1 {\n        return\n    }\n\n    \/\/ Populate all the numbers\n    for i := 2; i &lt;= limit; i++ {\n        myMap[i] = true\n    }\n\n    \/\/ Check the numbers and false all the multiples\n    for i := 2; i &lt;= limit; i++ {\n        for j := 2; (j * i) &lt;= limit; j++ {\n            if myMap[(i * j)] {\n                myMap[(i * j)] = false\n            }\n        }\n    }\n\n    \/\/ Append only the positive found\n    for k := range myMap {\n        if myMap[k] {\n            out = append(out, k)\n        }\n    }\n\n    sort.Ints(out)\n\n    return\n}<\/pre>\n\n\n\n<p>I used a map of <code>(int, boolean)<\/code>to add all the element up to the limit (13 in my example above)<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">Initial Map has\n\n[2] = true\n[3] = true\n[4] = true. .... [13] = true<\/pre>\n\n\n\n<p>Then I ran a simple for loop to iterate till the limit <code>13<\/code> on the map and mark all the multiples as false.<\/p>\n\n\n\n<p>So it starts with <code>2<\/code> till <code>13<\/code> checking for every multiple and marking it false.<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">2*2 = 4\n[4] = false\n2*3 = 6\n[6] = false\n2*4 = 8\n[8] = false\n...<\/pre>\n\n\n\n<p>and finally for all elements which have a true against it I add it to the <code>int[]<\/code> and return it.<\/p>\n\n\n\n<h3 class=\"has-text-align-center wp-block-heading\">&#8212; THE &#8211; END &#8212;<\/h3>\n","protected":false},"excerpt":{"rendered":"<p>Sieve is an ancient and an ingenious way of calculating primes. It recursively eliminates all the multiples of a particular number up till a range and the left overs are essentially primes. It was just a matter of defining the right data structure and computing the final set of primes package sieve import &#8220;sort&#8221; \/\/ [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":410,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[3],"tags":[],"class_list":["post-409","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-personal"],"_links":{"self":[{"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/posts\/409","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/comments?post=409"}],"version-history":[{"count":0,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/posts\/409\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/media\/410"}],"wp:attachment":[{"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/media?parent=409"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/categories?post=409"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.samarthya.me\/wps\/wp-json\/wp\/v2\/tags?post=409"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}