#include <bitset>       // bitset<N>
#include <cmath>        // sqrt()
#include <iostream>     
 
std::bitset<1000000> prim;
 
void eratosthenes()     // Siebverfahren
{   
  prim.set();           // alle Bits setzen
  prim[0]=false;
  prim[1]=false;        // keine Primzahlen 
  long const max  = prim.size();
  long const root = long(std::sqrt(max) + 0.5);
 
  for (long i = 2; i <= root; ++i)
  {
    for (long j = i+i; j < max; j+=i)
    {
      prim[j]=false;  // Vielfache löschen
    }
  }
}  
 
void ausgabe() 
{
  std::cout << "Alle Primzahlen <" << prim.size() << '\n';
  for (long i = 2; i < prim.size(); ++i)
  {
    if (prim[i])
    {
      std::cout << i << '\t';
    }
  }
  std::cout << '\n';
}  
 
int main() 
{
  std::cout << "Sieb des Eratosthenes\n";
  eratosthenes();  // 15 Sekunden
  ausgabe();       // 4 Minuten
}