INF.03Programowanie
Sito Eratostenesa (Liczby pierwsze)
Wydajny algorytm wyznaczania wszystkich liczb pierwszych z przedziału od 2 do zadanej liczby n poprzez wykreślanie wielokrotności.
Jak działa Sito Eratostenesa?
- Tworzymy tablicę wartości logicznych od 2 do n wypełnioną wartościami
true. - Zaczynamy od pierwszej liczby pierwszej (2) i wykreślamy (ustawiamy na
false) wszystkie jej wielokrotności (4, 6, 8...). - Przechodzimy do kolejnej niewykreślonej liczby i powtarzamy proces aż do
√n.
JAVASCRIPT
function sitoEratostenesa(max) {
const pierwsze = new Array(max + 1).fill(true);
pierwsze[0] = false;
pierwsze[1] = false;
for (let i = 2; i * i <= max; i++) {
if (pierwsze[i]) {
for (let j = i * i; j <= max; j += i) {
pierwsze[j] = false;
}
}
}
return pierwsze
.map((jestPierwsza, index) => jestPierwsza ? index : null)
.filter(n => n !== null);
}Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Sito Eratostenesa (Liczby pierwsze) lub rozpocznij trening.