title: Sieve of Eratosthenes for large numbers c++
body: <p>Just like this <a href="https://stackoverflow.com/questions/1954858/sieve-of-eratosthenes-algorithm">question</a>, I also am working on the sieve of Eratosthenes. Also from the book <em>"programming principles and practice using c++"</em>, chapter 4. I was able to implement it correctly and it is functioning exactly as the exercise asks.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  
  using namespace std;
  
  int main() {
      unsigned int amount = 0;
  
      cin &gt;&gt; amount;
  
      vector&lt;int&gt;numbers;
  
      for (unsigned int i = 0; i &lt;= amount; i++) {
          numbers.push_back(i);
      }
  
      for (unsigned int p = 2; p &lt; amount; p++) {
          if (numbers[p] == 0)
              continue;
  
          cout &lt;&lt; p &lt;&lt; '\n';
  
          for (unsigned int i = p + p; i &lt;= amount; i += p) {
              numbers[i] = false;
          }
      }
  
      return 0;
  }
  </code></pre>
  
  <p>Now, how would I be able to handle real big numbers in the <code>amount</code> input? The <code>unsigned int</code> type should allow me to enter a number of 2^32=4,294,967,296. But I can't, I run out of memory. Yes, I've done the math: storing 2^32 amount of int, 32 bits each. So 32/8*2^32=16 GiB of memory. I have just 4 GiB...</p>
  
  <p>So what I am really doing here is setting non-primes to zero. So I could use a boolean. But still, they would take 8 bits, so 1 byte each. Theoretical I could go to the limit for <code>unsigned int</code> (8/8*2^32=4 GiB), using some of my swap space for the OS and overhead. But I have a x86_64 PC, so what about numbers larger than 2^32?</p>
  
  <p>Knowing that primes are <a href="https://stackoverflow.com/questions/439870/why-are-primes-important-in-cryptography">important in cryptography</a>, there must be a more efficient way of doing this? And are there also ways to optimize the time needed to find all those primes?</p>