title: How to use less memory in Sieve_of_Eratosthenes
body: <p>I'm coding on a leetcode-like platform. There is a task: counter the number of primes below a given bound.</p>
  
  <p>I used the algorithm: <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes</a></p>
  
  <p>I copy the code from here: <a href="https://www.geeksforgeeks.org/sieve-of-eratosthenes/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/sieve-of-eratosthenes/</a> , except that I make <code>false</code> represents <code>isPrime</code> to avoid using <code>memset</code>. Here is my code:</p>
  
  <pre><code>void SieveOfEratosthenes(int n) 
  { 
      bool *prime = new bool[n+1]();  // initialized by false by default  
  
      for (int p=2; p*p&lt;=n; p++) 
      { 
          if (prime[p] == false) 
          { 
              for (int i=p*p; i&lt;=n; i += p) 
                  prime[i] = true; 
          } 
      } 
  
      for (int p=2; p&lt;=n; p++) 
         if (prime[p]) 
            cout &lt;&lt; p &lt;&lt; " "; 
  }
  </code></pre>
  
  <p>However, when I execute it, the platform tells me that I used too much memory in the case of <code>100 000 000</code> as the enter.</p>
  
  <p>I've checked that <code>sizeof(bool)</code> equals to <code>1</code>.</p>
  
  <p>Is there some way to use less memory for this piece of code?</p>