Sito Eratostenesa to algorytmn generujący liczby pierwsze z zakresu [2; n]
Specyfikacja
| 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 |
Zadanie - Liczby pierwsze
Liczba pierwsza to liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: 1 i samą siebie. Przykłady liczb pierwszych: 7 11 29
Liczba 21 nie jest liczbą pierwszą, ponieważ oprócz liczby 1 i 21 jej dzielnikami są także 3 i 7.
W pliku o nazwie liczby.txt umieszczono w kolejnych wierszach 500 liczb całkowitych dodatnich, po jednej w wierszu, z których każda liczba ma co najwyżej 6 cyfr.
Napisz program, za pomocą którego otrzymasz tylko te liczby z pliku liczby.txt, które są kwadratami liczb pierwszych.
Na przykład liczba 49 jest kwadratem liczby pierwszej 49 = 72