title: Segmented Sieve of Eratosthenes?
body: <p>It's easy enough to make a simple sieve:</p>
  
  <pre><code>for (int i=2; i&lt;=N; i++){
      if (sieve[i]==0){
          cout &lt;&lt; i &lt;&lt; " is prime" &lt;&lt; endl;
          for (int j = i; j&lt;=N; j+=i){
              sieve[j]=1;
          }
      }
      cout &lt;&lt; i &lt;&lt; " has " &lt;&lt; sieve[i] &lt;&lt; " distinct prime factors\n";
  }
  </code></pre>
  
  <p>But what about when N is very large and I can't hold that kind of array in memory? I've looked up segmented sieve approaches and they seem to involve finding primes up until sqrt(N) but I don't understand how it works. What if N is very large (say 10^18)?</p>