| II Mistrzostwa Wielkopolski w Programowaniu Zespołowym | 3-4 grudnia 2004 |
|
|
Liczby pierwsze to te liczby naturalne większe od 1, które mają tylko dwa podzielniki naturalne dodatnie: jedynkę i samą siebie. Liczbę naturalną większą od 1, która nie jest liczbą pierwszą, nazywamy liczbą złożoną. Liczba 1 nie jest ani liczbą pierwszą, ani złożoną.
Liczby naturalne dodatnie A1, A2, …, AN nazywamy względnie pierwszymi, jeśli ich największym wspólnym podzielnikiem jest liczba 1. Oznacza to, że żadna liczba naturalna większa od 1 nie dzieli całkowicie jednocześnie wszystkich liczb A1, A2, …, AN.
Liczba s-pierwsza, to taka liczba naturalna większa od 1, dla której wszystkie liczby naturalne większe od 1, a mniejsze od niej, będące względnie pierwsze z nią, są liczbami pierwszymi.
Dla podanej liczby sprawdź, czy jest ona liczbą s-pierwszą, czy też nie.
Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych. Każdy zestaw danych znajduje się w osobnej linii i składa się z jednej liczby naturalnej N (2 ≤ N ≤ 2000000000), będącej liczbą, którą trzeba zbadać.
Dla każdej liczby, która pojawi się w zestawie danych na wejściu należy w osobnej linii wypisać TAK jeśli liczba jest s-pierwsza, albo NIE w przeciwnym przypadku.
2 6 7
TAK NIE