/******************************************************************************
Welcome to GDB Online.
Algorytm Sito Eratostenesa
Lista kroków algorytmu:
Krok 0. Wczytaj wartość n.
Krok 1. Przypisz elementom tablicy T wartości początkowe 1
Krok 2. Przypisz najmniejszą liczbę pierwszą zmiennej i: i=2
Krok 3. Znajdź wszystkie wielokrotności liczby i z zakresu [2-i; n] oraz oznacz je jako liczby złożone, czyli zmień tym elementom tablicy T wartości na 0
Krok 4. Poszukaj kolejnej liczby pierwszej większej od i z zakresu [i+1; n] oraz - jeśli zostanie znaleziona - przejdź do kroku 3, w przeciwnym przypadku przejdź do kroku 5
Krok 5 Wypisz wszystkie liczby pierwsze z zakresu [2; n], czyli indeksy tych elementów tablicy T, których wartość jest równa 1. Zakończ algorytm
*******************************************************************************/
#include <iostream>
using namespace std;
int main()
{
int i, j;
int N = 100001; // Deklaracja wielkości tablicy - koniec przedziału, w którym znajdujemy liczby pierwsze
bool T[N];
for (i=2; i<N; i++) T[i] = 1;
i=2;
while (i<N)
{
j = 2*i;
while (j < N)
{
T[j] = 0;
j = j+i;
}
i++;
}
// wypisanie wyniku
for (i=2; i<N; i++)
{
if (T[i])
cout << i << " ";
}
return 0;
}
