Sito Eratostenesa

Algorytmy z egzaminu różnymi sposobami - JavaScript od podstaw: konsola (JavaScript)

Inne podejście, gdy potrzebujemy WSZYSTKICH liczb pierwszych do jakiejś granicy. Zamiast sprawdzać każdą liczbę osobno, wykreślamy wielokrotności: tablica `isComposite` zaczyna od samych `false`, a dla każdej niewykreślonej liczby `p` wykreślamy `p * p`, `p * p + p` itd. Co zostanie niewykreślone, jest pierwsze. `new Array(n + 1).fill(false)` tworzy tablicę o podanej długości.

function sieve(n) {
  const isComposite = new Array(n + 1).fill(false);
  const primes = [];
  for (let p = 2; p <= n; p++) {
    if (isComposite[p]) continue;
    primes.push(p);
    for (let m = p * p; m <= n; m += p) {
      isComposite[m] = true;
    }
  }
  return primes;
}

const primes = sieve(50);
console.log(primes.join(' '));
console.log('Do 50:', primes.length, 'do 1000:', sieve(1000).length);

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu JavaScript od podstaw: konsola·Zaloguj się, aby zapisać postęp na koncie.