|
|
| (Není zobrazeno 86 mezilehlých verzí od 5 dalších uživatelů.) |
| Řádek 1: |
Řádek 1: |
| <source lang="cpp">
| | TEST |
| #include <iostream>
| | testík |
| #include <vector>
| | xxx |
| | xxxxxx |
|
| |
|
| 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();
| | test... |
| 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);
| |
|
| |
| }
| |
| </source>
| |
