Sieb des Eratosthenes

#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>

using namespace std;

typedef unsigned long primtyp;

int main(int argc, char** argv)
{
  primtyp maxprims = atol(argv[1]) - 1;             // 200000000000 max bei 16GB Ram
    
  primtyp anzahl_prims_array    = (maxprims-1)/2;   // Laenge des notwendigen arrays

  primtyp anzahl_prims      = (maxprims-1)/2;       // Wird runtergezaehlt um Anzahl zu erhalten
   
  primtyp wurzel_maxprims   = sqrt(anzahl_prims);   // Man muss nur bis zur Wurzel der Anzahl gehen, um zu streichen
    
  vector<bool> menge(anzahl_prims_array,1);         // Array reservieren und mit Einsen fuellen
        
  for ( primtyp j = 1; j<= wurzel_maxprims ;j++)    // Gehe von 1 (zweiter Eintrag im Array, steht fuer die Drei) bis Wurzel(maxprim) um Vielfache zu streichen
  {       
      if( menge[j] == 1 )                           // Falls Zahl ungestrichen...
      {           
         for( primtyp k = (2*j)*(j+1); k < anzahl_prims_array; k+=(2*j+1) )   // Streiche alle Vielfachen und vermeide Doppelstreichungen
         {
           if( menge[k] != 0 )                      // Falls zahl noch ungestrichen ...
           {
                 menge[k] = 0;                      // Zahl streichen, und ...
                 anzahl_prims--;                    // Eine Primzahl weniger vermerken
           }
         }      
      }
   }
                                                           
   cout << anzahl_prims << endl;
 
   return 0;
}
  

Performance:

Setup

Results