Ja sam robiłem podobne zadanie na SPOJu. Tylko program nie działa tak jak należy, bo wyświetla wartość "NIE" dla każdej liczby. Na razie nie mam czasu żeby w tym grzebać - dam Ci kod i jak chcesz, to sam pomyśl nad tym i możesz mi przy okazji wysłać poprawne rozwiązanie, bo od dłuższego czasu się z tym głowie. ^^
#include <iostream>
using namespace std;
const int n = 100;
bool numbersTable[n + 1]; // tablica o indeksach od 0 do 100 | wszystkie false (czyli: 0);
int main()
{
int liczba, test;
cin >> test;
while (test--)
{
cin >> liczba;
for (int i = 2; i*i <= n; i++ ) // przeszukuj liczby od 2 do sqrt(n), 0 i 1 nie s¹ liczbami pierwszymi
{
if (numbersTable[i] == true) // je¿eli dana liczba jest ju¿ wykreœlona
continue; // to przejdŸ do kolejnej
for (int j = 2*i ; j <= n; j += i) // przejdŸ od liczby 2*i do n przesuwaj¹c siê o i
numbersTable[j] = true; // i ka¿d¹ z nich usuwaj ze zbioru
}
for (int i = 2; i <= n; i++) // przeszukaj liczby od 2 do n
{
if (numbersTable[i] == false);// jeœli liczba nie zosta³a usuniêta ze zbioru
if (i == liczba)
cout << "TAK" << endl;
else
cout << "NIE" << endl;
}
}
return 0;
}