{"id":2022,"date":"2021-09-24T18:28:45","date_gmt":"2021-09-24T12:58:45","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2022"},"modified":"2022-07-05T16:46:42","modified_gmt":"2022-07-05T11:16:42","slug":"sieve-of-eratosthenes","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/sieve-of-eratosthenes\/","title":{"rendered":"Sieve of Eratosthenes: Finding All Prime Numbers"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#simple-approach\">Simple Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#-java-implementation\"> Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#efficient-approach-sieve-of-eratosthenes\">Efficient Approach: Sieve of Eratosthenes<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#dry-run-of-the-above-approach\">Dry run of the above approach<\/a><\/li><li><a href=\"#c-implementation-efficient-approach\">C++ Implementation Efficient Approach<\/a><\/li><li><a href=\"#--java-implementation-of-efficient-approach\">  Java Implementation of Efficient Approach<\/a><\/li><li><a href=\"#python-implementation-of-efficient-approach\">Python Implementation of Efficient Approach<\/a><\/li><li><a href=\"#analysis-of-time-complexity\">Analysis of Time Complexity<\/a><\/li><\/ul><li><a href=\"#conclusion\">Conclusion<\/a><\/li><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.<\/p>\n\n\n\n<p>A prime number is a number that is divisible by only two numbers &#8211; themselves and 1<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<p><strong>Input:<\/strong> n =10<br><strong>Output:<\/strong> 2 3 5 7<br><strong>Explanation:<\/strong> Only 4 prime numbers are there which are less than or equal to 10.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"613\"  height=\"244\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Finding Prime Numbers\"  class=\"wp-image-2140 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 613px) 100vw, 613px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/2-4.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/2-4.jpg 613w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/2-4-300x119.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/2-4-380x151.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/2-4-550x219.jpg 550w\" ><figcaption>Finding Prime Numbers<\/figcaption><\/figure><\/div>\n\n\n\n<p><strong>Input:<em> <\/em><\/strong>n = 20&nbsp;<br><strong>Output<\/strong>: 2 3 5 7 11 13 17 19<br><strong>Explanation: <\/strong>All above numbers are prime which are less than or equal to 20.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"simple-approach\">Simple Approach<\/h2>\n\n\n\n<p>Iterate from 2 to N, and check for prime. If it is a prime number, print the number.&nbsp; Below is the implementation of the above approach<\/p>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int checkPrime(int n) {\n   if (n &lt;= 1)\n      return 0;\n\n   for (int i = 2; i &lt; n; i++)\n      if (n % i == 0)\n         return 0;\n\n   return 1;\n}\n\/\/ Function to print all the prime numbers from \n\/\/ range 2 to n \nvoid printPrime(int n) {\n   for (int i = 2; i &lt;= n; i++) {\n      if (checkPrime(i))\n         cout &lt;&lt; i &lt;&lt; \" \";\n   }\n}<\/pre>\n\n\n\n<h3 id=\"-java-implementation\"><span id=\"java-implementation\"> Java Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Interviewbit {\n   static int isPrime(int n) {\n      for (int i = 2; i &lt; n; i++)\n         if (n % i == 0)\n            return 0;\n\n      return 1;\n   }\n\n   static void printPrime(int n) {\n      for (int i = 2; i &lt;= n; i++) {\n         if (isPrime(i))\n            System.out.print(i + \" \");\n      }\n   }\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> def isPrime(n):\n     \n    # Corner case\n    if n &lt;= 1 :\n        return False\n \n    # check from 2 to n-1\n    for i in range(2, n):\n        if n % i == 0:\n            return False\n \n    return True\n \n# Function to print primes\ndef printPrime(n):\n    for i in range(2, n + 1):\n        if isPrime(i):\n            print(i, end = \" \")<\/pre>\n\n\n\n<p><strong>Time complexity:<\/strong> O(N*N), Where N is the number.<br><strong>Space complexity:<\/strong> O(1)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"efficient-approach-sieve-of-eratosthenes\">Efficient Approach: Sieve of Eratosthenes<\/h2>\n\n\n\n<p>The <strong>sieve of Eratosthenes<\/strong> is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so. Following is the algorithm to find all the prime numbers less than or equal to a given integer <em>n<\/em> by the Eratosthenes method:&nbsp;<\/p>\n\n\n\n<p>When the algorithm terminates, all the numbers in the list that are not marked are prime.&nbsp;<\/p>\n\n\n\n<ul><li>Firstly write all the numbers from&nbsp; 2,3,4\u2026. n<\/li><li>Now take the first prime number and mark all its multiples as visited.<\/li><li>Now when you move forward take another number which is unvisited yet and then follow the same step-2 with that number.<\/li><li>All numbers in the list left unmarked when the algorithm ends are referred to as prime numbers.<\/li><\/ul>\n\n\n\n<h3 id=\"dry-run-of-the-above-approach\">Dry run of the above approach<\/h3>\n\n\n\n<p><strong>Step 1: The numbers between 1 and 100 are listed in the table below.<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>1<\/td><td>2<\/td><td>3<\/td><td>4<\/td><td>5<\/td><td>6<\/td><td>7<\/td><td>8<\/td><td>9<\/td><td>10<\/td><\/tr><tr><td>11<\/td><td>12<\/td><td>13<\/td><td>14<\/td><td>15<\/td><td>16<\/td><td>17<\/td><td>18<\/td><td>19<\/td><td>20<\/td><\/tr><tr><td>21<\/td><td>22<\/td><td>23<\/td><td>24<\/td><td>25<\/td><td>26<\/td><td>27<\/td><td>28<\/td><td>29<\/td><td>30<\/td><\/tr><tr><td>31<\/td><td>32<\/td><td>33<\/td><td>34<\/td><td>35<\/td><td>36<\/td><td>37<\/td><td>38<\/td><td>39<\/td><td>40<\/td><\/tr><tr><td>41<\/td><td>42<\/td><td>43<\/td><td>44<\/td><td>45<\/td><td>46<\/td><td>47<\/td><td>48<\/td><td>49<\/td><td>50<\/td><\/tr><tr><td>51<\/td><td>52<\/td><td>53<\/td><td>54<\/td><td>55<\/td><td>56<\/td><td>57<\/td><td>58<\/td><td>59<\/td><td>60<\/td><\/tr><tr><td>61<\/td><td>62<\/td><td>63<\/td><td>64<\/td><td>65<\/td><td>66<\/td><td>67<\/td><td>68<\/td><td>69<\/td><td>70<\/td><\/tr><tr><td>71<\/td><td>72<\/td><td>73<\/td><td>74<\/td><td>75<\/td><td>76<\/td><td>77<\/td><td>78<\/td><td>79<\/td><td>80<\/td><\/tr><tr><td>81<\/td><td>82<\/td><td>83<\/td><td>84<\/td><td>85<\/td><td>86<\/td><td>87<\/td><td>88<\/td><td>89<\/td><td>90<\/td><\/tr><tr><td>91<\/td><td>92<\/td><td>93<\/td><td>94<\/td><td>95<\/td><td>96<\/td><td>97<\/td><td>98<\/td><td>99<\/td><td>100<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Step 2: The next step is to write in bold all the multiples of 2, except 2 itself.<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>1<\/td><td>2<\/td><td>3<\/td><td><strong>4<\/strong><\/td><td>5<\/td><td><strong>6<\/strong><\/td><td>7<\/td><td><strong>8<\/strong><\/td><td>9<\/td><td><strong>10<\/strong><\/td><\/tr><tr><td>11<\/td><td><strong>12<\/strong><\/td><td>13<\/td><td><strong>14<\/strong><\/td><td>15<\/td><td><strong>16<\/strong><\/td><td>17<\/td><td><strong>18<\/strong><\/td><td>19<\/td><td><strong>20<\/strong><\/td><\/tr><tr><td>21<\/td><td><strong>22<\/strong><\/td><td>23<\/td><td><strong>24<\/strong><\/td><td>25<\/td><td><strong>26<\/strong><\/td><td>27<\/td><td><strong>28<\/strong><\/td><td>29<\/td><td><strong>30<\/strong><\/td><\/tr><tr><td>31<\/td><td><strong>32<\/strong><\/td><td>33<\/td><td><strong>34<\/strong><\/td><td>35<\/td><td><strong>36<\/strong><\/td><td>37<\/td><td><strong>38<\/strong><\/td><td>39<\/td><td><strong>40<\/strong><\/td><\/tr><tr><td>41<\/td><td><strong>42<\/strong><\/td><td>43<\/td><td><strong>44<\/strong><\/td><td>45<\/td><td><strong>46<\/strong><\/td><td>47<\/td><td><strong>48<\/strong><\/td><td>49<\/td><td><strong>50<\/strong><\/td><\/tr><tr><td>51<\/td><td><strong>52<\/strong><\/td><td>53<\/td><td><strong>54<\/strong><\/td><td>55<\/td><td><strong>56<\/strong><\/td><td>57<\/td><td><strong>58<\/strong><\/td><td>59<\/td><td><strong>60<\/strong><\/td><\/tr><tr><td>61<\/td><td><strong>62<\/strong><\/td><td>63<\/td><td><strong>64<\/strong><\/td><td>65<\/td><td><strong>66<\/strong><\/td><td>67<\/td><td><strong>68<\/strong><\/td><td>69<\/td><td><strong>70<\/strong><\/td><\/tr><tr><td>71<\/td><td><strong>72<\/strong><\/td><td>73<\/td><td><strong>74<\/strong><\/td><td>75<\/td><td><strong>76<\/strong><\/td><td>77<\/td><td><strong>78<\/strong><\/td><td>79<\/td><td><strong>80<\/strong><\/td><\/tr><tr><td>81<\/td><td><strong>82<\/strong><\/td><td>83<\/td><td>84<\/td><td>85<\/td><td><strong>86<\/strong><\/td><td>87<\/td><td><strong>88<\/strong><\/td><td>89<\/td><td><strong>90<\/strong><\/td><\/tr><tr><td>91<\/td><td><strong>92<\/strong><\/td><td>93<\/td><td><strong>94<\/strong><\/td><td>95<\/td><td><strong>96<\/strong><\/td><td>97<\/td><td><strong>98<\/strong><\/td><td>99<\/td><td><strong>100<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Step 3: Now bold all multiples of 3, 5, and 7 and only leave these numbers.<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>1<\/td><td>2<\/td><td>3<\/td><td><strong>4<\/strong><\/td><td>5<\/td><td><strong>6<\/strong><\/td><td>7<\/td><td><strong>8<\/strong><\/td><td>9<\/td><td><strong>10<\/strong><\/td><\/tr><tr><td>11<\/td><td><strong>12<\/strong><\/td><td>13<\/td><td><strong>14<\/strong><\/td><td><strong>15<\/strong><\/td><td><strong>16<\/strong><\/td><td>17<\/td><td><strong>18<\/strong><\/td><td>19<\/td><td><strong>20<\/strong><\/td><\/tr><tr><td><strong>21<\/strong><\/td><td><strong>22<\/strong><\/td><td>23<\/td><td><strong>24<\/strong><\/td><td><strong>25<\/strong><\/td><td><strong>26<\/strong><\/td><td><strong>27<\/strong><\/td><td><strong>28<\/strong><\/td><td>29<\/td><td><strong>30<\/strong><\/td><\/tr><tr><td>31<\/td><td><strong>32<\/strong><\/td><td><strong>33<\/strong><\/td><td><strong>34<\/strong><\/td><td><strong>35<\/strong><\/td><td><strong>36<\/strong><\/td><td>37<\/td><td><strong>38<\/strong><\/td><td><strong>39<\/strong><\/td><td><strong>40<\/strong><\/td><\/tr><tr><td>41<\/td><td><strong>42<\/strong><\/td><td>43<\/td><td><strong>44<\/strong><\/td><td><strong>45<\/strong><\/td><td><strong>46<\/strong><\/td><td>47<\/td><td><strong>48<\/strong><\/td><td><strong>49<\/strong><\/td><td><strong>50<\/strong><\/td><\/tr><tr><td><strong>51<\/strong><\/td><td><strong>52<\/strong><\/td><td>53<\/td><td><strong>54<\/strong><\/td><td><strong>55<\/strong><\/td><td><strong>56<\/strong><\/td><td><strong>57<\/strong><\/td><td><strong>58<\/strong><\/td><td>59<\/td><td><strong>60<\/strong><\/td><\/tr><tr><td>61<\/td><td><strong>62<\/strong><\/td><td><strong>63<\/strong><\/td><td><strong>64<\/strong><\/td><td><strong>65<\/strong><\/td><td><strong>66<\/strong><\/td><td>67<\/td><td><strong>68<\/strong><\/td><td><strong>69<\/strong><\/td><td><strong>70<\/strong><\/td><\/tr><tr><td>71<\/td><td><strong>72<\/strong><\/td><td>73<\/td><td><strong>74<\/strong><\/td><td><strong>75<\/strong><\/td><td><strong>76<\/strong><\/td><td><strong>77<\/strong><\/td><td><strong>78<\/strong><\/td><td>79<\/td><td><strong>80<\/strong><\/td><\/tr><tr><td><strong>81<\/strong><\/td><td><strong>82<\/strong><\/td><td>83<\/td><td><strong>84<\/strong><\/td><td><strong>85<\/strong><\/td><td><strong>86<\/strong><\/td><td><strong>87<\/strong><\/td><td><strong>88<\/strong><\/td><td>89<\/td><td><strong>90<\/strong><\/td><\/tr><tr><td><strong>91<\/strong><\/td><td><strong>92<\/strong><\/td><td><strong>93<\/strong><\/td><td><strong>94<\/strong><\/td><td><strong>95<\/strong><\/td><td><strong>96<\/strong><\/td><td>97<\/td><td><strong>98<\/strong><\/td><td><strong>99<\/strong><\/td><td><strong>100<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Step 4: Since the multiples of 11, 13, 17, and 19 are not present on the list, 1 is finally shaded because it is not prime.<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>1<\/strong><\/td><td><strong>2<\/strong><\/td><td>3<\/td><td><strong>4<\/strong><\/td><td>5<\/td><td><strong>6<\/strong><\/td><td>7<\/td><td><strong>8<\/strong><\/td><td>9<\/td><td><strong>10<\/strong><\/td><\/tr><tr><td>11<\/td><td><strong>12<\/strong><\/td><td>13<\/td><td><strong>14<\/strong><\/td><td><strong>15<\/strong><\/td><td><strong>16<\/strong><\/td><td>17<\/td><td><strong>18<\/strong><\/td><td>19<\/td><td><strong>20<\/strong><\/td><\/tr><tr><td><strong>21<\/strong><\/td><td><strong>22<\/strong><\/td><td>23<\/td><td><strong>24<\/strong><\/td><td><strong>25<\/strong><\/td><td><strong>26<\/strong><\/td><td><strong>27<\/strong><\/td><td><strong>28<\/strong><\/td><td>29<\/td><td><strong>30<\/strong><\/td><\/tr><tr><td>31<\/td><td><strong>32<\/strong><\/td><td><strong>33<\/strong><\/td><td><strong>34<\/strong><\/td><td><strong>35<\/strong><\/td><td><strong>36<\/strong><\/td><td>37<\/td><td><strong>38<\/strong><\/td><td><strong>39<\/strong><\/td><td><strong>40<\/strong><\/td><\/tr><tr><td>41<\/td><td><strong>42<\/strong><\/td><td>43<\/td><td><strong>44<\/strong><\/td><td><strong>45<\/strong><\/td><td><strong>46<\/strong><\/td><td>47<\/td><td>48<\/td><td><strong>49<\/strong><\/td><td><strong>50<\/strong><\/td><\/tr><tr><td><strong>51<\/strong><\/td><td><strong>52<\/strong><\/td><td>53<\/td><td><strong>54<\/strong><\/td><td><strong>55<\/strong><\/td><td><strong>56<\/strong><\/td><td><strong>57<\/strong><\/td><td><strong>58<\/strong><\/td><td>59<\/td><td><strong>60<\/strong><\/td><\/tr><tr><td>61<\/td><td><strong>62<\/strong><\/td><td><strong>63<\/strong><\/td><td><strong>64<\/strong><\/td><td><strong>65<\/strong><\/td><td><strong>66<\/strong><\/td><td>67<\/td><td><strong>68<\/strong><\/td><td><strong>69<\/strong><\/td><td><strong>70<\/strong><\/td><\/tr><tr><td>71<\/td><td><strong>72<\/strong><\/td><td>73<\/td><td><strong>74<\/strong><\/td><td><strong>75<\/strong><\/td><td><strong>76<\/strong><\/td><td><strong>77<\/strong><\/td><td><strong>78<\/strong><\/td><td>79<\/td><td><strong>80<\/strong><\/td><\/tr><tr><td><strong>81<\/strong><\/td><td><strong>82<\/strong><\/td><td>83<\/td><td><strong>84<\/strong><\/td><td><strong>85<\/strong><\/td><td><strong>86<\/strong><\/td><td><strong>87<\/strong><\/td><td><strong>88<\/strong><\/td><td>89<\/td><td><strong>90<\/strong><\/td><\/tr><tr><td><strong>91<\/strong><\/td><td><strong>92<\/strong><\/td><td><strong>93<\/strong><\/td><td><strong>94<\/strong><\/td><td><strong>95<\/strong><\/td><td><strong>96<\/strong><\/td><td>97<\/td><td><strong>98<\/strong><\/td><td><strong>99<\/strong><\/td><td><strong>100<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Step 5: The unshaded numbers are prime. They include:<\/strong><\/p>\n\n\n\n<p>2, 3, 5,7, 11, 13,17,19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97.<\/p>\n\n\n\n<h3 id=\"c-implementation-efficient-approach\">C++ Implementation Efficient Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void SieveOfEratosthenes(int n)\n{\n    bool prime[n + 1];\n    memset(prime, true, sizeof(prime));\n \n    for (int p = 2; p * p &lt;= n; p++)\n    {\n        if (prime[p] == true)\n        {\n            for (int i = p * p; i &lt;= n; i += p)\n                prime[i] = false;\n        }\n    }\n    for (int p = 2; p &lt;= n; p++)\n        if (prime[p])\n            cout &lt;&lt; p &lt;&lt; \" \";\n}<\/pre>\n\n\n\n<h3 id=\"--java-implementation-of-efficient-approach\"><span id=\"java-implementation-of-efficient-approach\">  Java Implementation of Efficient Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class SieveOfEratosthenes {\n\tvoid sieveOfEratosthenes(int n)\n\t{\n\t\tboolean prime[] = new boolean[n + 1];\n\t\tfor (int i = 0; i &lt;= n; i++)\n\t\t\tprime[i] = true;\n\n\t\tfor (int p = 2; p * p &lt;= n; p++){\n\t\t\tif (prime[p] == true)\n\t\t\t{\n\t\t\t\tfor (int i = p * p; i &lt;= n; i += p)\n\t\t\t\t\tprime[i] = false;\n\t\t\t}\n\t\t}\n\n\t\tfor (int i = 2; i &lt;= n; i++)\n\t\t{\n\t\t\tif (prime[i] == true)\n\t\t\t\tSystem.out.print(i + \" \");\n\t\t}\n\t}\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation-of-efficient-approach\">Python Implementation of Efficient Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> def SieveOfEratosthenes(n):\n    prime = [True for i in range(n+1)]\n    p = 2\n    while (p * p &lt;= n):\n        if (prime[p] == True):\n \n            # Update all multiples of p\n            for i in range(p * p, n+1, p):\n                prime[i] = False\n        p += 1\n \n    # Print all prime numbers\n    for p in range(2, n+1):\n        if prime[p]:\n            print p,<\/pre>\n\n\n\n<p><strong>Time complexity of Sieve of Eratosthenes<\/strong>: <\/p>\n\n\n\n<p><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  width=\"155\"  height=\"19\"  class=\" pk-lazyload\"  data-pk-sizes=\"auto\"  data-pk-src=\"https:\/\/lh5.googleusercontent.com\/2UEp045U0Ld2VPA1MXjwosB9CihgkBFfv5m3e_QOdE_CMdQA_1n7kDQnzVjvOopMftyqCsfjAA02aODCYyS4ETXmknZvEMe63NM7JOpQUsLYu4g00Bk4MRJLdJ1UZj-7d1bMybTAUIHghmIadA\" ><\/p>\n\n\n\n<p><strong>Space complexity:<\/strong> O(1)<\/p>\n\n\n\n<h3 id=\"analysis-of-time-complexity\">Analysis of Time Complexity<\/h3>\n\n\n\n<ul><li><strong>PREREQUISITE: <\/strong>Time complexity of the Harmonic Series is O(logN), when N is tending to infinity.<\/li><li>If we analyze our sieve for larger numbers then we can see .<ul><li>The inner loop at each iteration can be expressed by:<\/li><li>i=2, the inner loop will be executed \u2192 upper bound is (n\/2) times<\/li><li>i=3, the inner loop will be executed \u2192 upper bound is (n\/3) times<\/li><li>i=5, the inner loop will be executed \u2192 upper bound is (n\/5) times<\/li><li>\u2026<\/li><li>i=n(if prime number), the inner loop will be executed \u2192 upper bound is 1 times.<\/li><\/ul><\/li><li>The above series time complexity is less than harmonic series:&nbsp;<ul><li>n\/2 + n\/4 + ..+ 1 \u2192 n (1\/2 + 1\/3 + 1\/4 + \u2026 1\/n),&nbsp;<\/li><\/ul><\/li><li>Hence, the run loop times should be&nbsp;<ul><li>n (1\/2 + 1\/3 + 1\/5 + 1\/7 + 1\/ 11 + 1\/13 + \u2026).= logn That is why, in some article,&nbsp;<\/li><\/ul><\/li><li>The time complexity is defined in O(nloglogn).<\/li><\/ul>\n\n\n\n<h2 id=\"conclusion\">Conclusion<\/h2>\n\n\n\n<p>The outer loop is a general for-loop from 1 to N, the time complexity is O(N). The total time complexity is O(NloglogN).<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/all-factors\/\" target=\"_blank\">All Factors<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/prime-sum\/\" target=\"_blank\">Prime Sum<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/prime-numbers\/\" target=\"_blank\">Prime Numbers<\/a><\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p id=\"how-fast-is-sieve-of-eratosthenes\"><strong>Q: How fast is Sieve of Eratosthenes?<\/strong><br><strong>A:<\/strong> It is very fast as it can store prime numbers up to the 1e7 range easily.<\/p>\n\n\n\n<p id=\"how-do-you-improve-the-sieve-of-eratosthenes\"><strong>Q: How do you improve the sieve of Eratosthenes?<\/strong><br><strong>A:<\/strong> We can further improve the sieve to O(n) by writing it to an iterative sieve.<\/p>\n\n\n\n<p id=\"how-does-the-sieve-of-eratosthenes-work\"><strong>Q: How does the Sieve of Eratosthenes work?<\/strong><br><strong>A:<\/strong> It works on the principle of cancellation of prime factors.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a number n, print all primes smaller than or equal to n. It is also&hellip;\n","protected":false},"author":5,"featured_media":2141,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[354,353],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2022"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2022"}],"version-history":[{"count":12,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2022\/revisions"}],"predecessor-version":[{"id":21994,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2022\/revisions\/21994"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2141"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2022"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2022"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2022"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}