Sito Eratostenesa

Dodaj zakładkę 
Autor: 
Trudność: 
2
Typ rozwiązania: 
Wektor
Dziedzina: 

Sito Eratostenesa jest algorytmem, który umożliwia wyznaczanie liczb pierwszych z zadanego przedziału [2,n]. Algorytm działa w następujący sposób:

-wybieramy najmniejszą liczbę z przedziału i wykreślamy jej wielokrotności (czyli wykreślamy wielokrotności 2: 4,6,8 itd)

-wybieramy najmniejszą niewykreśloną liczbę i wykreślamy jej wielokrotności. Powtarzamy ten krok do momentu, gdy liczba, której wielokrotność wykreślamy, będzie większa niż  \(\sqrt{n}\)

-liczby, które pozostały po wykreślaniu są liczbami pierwszymi

Wypisz w wektorze, jakie liczby z zakresu 1800-2000 pozostaną po 6 iteracjach wykreślania (w kolejności rosnącej).

 

Nierozwiązane