C++ Bc. 3 cpp

#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=1; 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=1; i<=N; i++)
    if (p[i])
      prvocisla.push_back(i);

}

[ Zpět ]