GeoWikiCZ:Pískoviště

#include <iostream>
#include <vector>

typedef std::vector<int> Prvocisla;
 
void erathosthenovo_sito(int N, Prvocisla& prvocisla);
 
int main()
{
  Prvocisla p;
 
  erathosthenovo_sito (100, p);
 
  for (Prvocisla::const_iterator i=p.begin(), e=p.end(); i!=e; ++i)
      std::cout << *i << " ";
 
  std::cout << "\n";
}
 
void erathosthenovo_sito(int N, Prvocisla& prvocisla)
{
  // nejprve vymazeme obsah vystupniho seznamu

  prvocisla.clear();
  if (N <= 0) return;
 
  // Naplnim seznam kandidatu na prvocisla hodnotami od 1 do
  // N. Protoze jsou standardni kontejnery indexovany od nuly,
  // vytvorim kontejner o velikosti N+1 prvku a nulty prvek ignoruji
   
  // Poznamka: p[0] bude inicializovano na nulu, protoze se v
  // sablonach pro datove cleny pouzivaji implicitni konstruktory a i
  // zakladni ciselne typy jsou inicializovany na nulu, tj. napr. p[0]
  // = int();
   
  Prvocisla p(N+1);
  for (int i=2; i<=N; i++) p[i] = i;
 
  // nyni prochazim seznam prvocisel. V seznamu kandidatu oznacim vzdy
  // vsechny nasobky kazdeho prvocisla nulou (nejsou to prvocisla)
 
  for (int i=2; 2*i<=N; i++)
    if (p[i] != 0)
      {
        int k = 2*i;
        while (k <= N)
          {
            p[k] = 0;
            k += i;
          }
      }
 
  // Zkopirujeme vsechna nalezena prvocisla do vystupnho seznamu
 
  for (int i=2; i<=N; i++)
    if (p[i])
      prvocisla.push_back(i);
 
}