JS - sito eratostenesa

Poznajemy ciekawy algorytm pozwalający nam wygenerować liczby pierwsze w zakresie do podanej liczby. Do dzieła.

Algorytm działa tak:

Tworzy listę liczb od 2 do n, na przykład od 2 do 30
Liczba pierwsza to liczba większa od 1, która ma tylko 2 dzielniki (1 i samą siebie)
Bierzemy pierwszą liczbę czyli 2 i skreślamy wszystkie liczby podzielne przez 2
Bierzemy następną liczbę (3), sprawdzamy czy nie jest skreślona i skreślamy wszystkie liczby podzielne przez 3
Bierzemy 4, sprawdzamy czy skreślona, skreślona, idziemy dalej
Bierzemy 5, sprawdzamy, czy skreślona, skreślamy wszystkie liczby podzielne przez 5

Ok, wygląda to tak:

function sieveOfEratosthenes(num){

    let descendingArray = Array.from({length: num-1}, (_, i) => {
        return num-i;
    });

    let excluded = new Set();
    let output = [];

    while(descendingArray.length > 0){
         
         let currNumber = descendingArray.pop();

         if(excluded.has(currNumber))
            continue;

         for(let n = currNumber+1; n <= num; n++){
             if(n % currNumber === 0){
                excluded.add(n);
             }
         }

         output.push(currNumber);
    }

    return output;
}

console.log(sieveOfEratosthenes(30));
//[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ]

Czyli:

generujemy liczby od n do 2 (tutaj od 30 do 2)
tworzymy zbiór wykluczonych (mogą być dodawane po kilka razy, dlatego zbiór)
tworzymy tablicę output
tak długo jak nasz stos liczb od 2 do n (30) ma elementy, zrzucamy ze stosu zaczynając od 2
sprawdzamy, czy 2 nie zostało już wykluczone
przechodzimy po liczbach od 3 do 3 i sprawdzamy które z nich % 2 dają 0 (są podzielne przez 2) i je do wykluczonych dodajemy.
na koniec dodajemy 2 do wyniku
jako że 3 nie jest w wykluczonych robimy od 4 do 30, sprawdzamy które z nich % 3 dają 0, dodajemy do wykluczonych, dopisujemy 3
4 jest w wykluczonych idziemy dalej
5, skreślamy podzielne przez 5, dopisujemy 5, idziemy dalej
6 już dwa razy zostało skreślone (dlatego set choć możemy dodać warunek)

Generalnie chodzi tu bardziej o to, aby załapać trochę matematyki i matematycznych algorytmów, niż zrobić super optymalny algorytm.

Bo optymalny algorytm (chodzi o samą pętlę) wygląda mniej więcej tak:

function sieveOfEratosthenes(n) {
    let primes = Array(n + 1).fill(true);  // Assume all numbers in array are prime
    primes[0] = primes[1] = false;         // Except for 0 and 1
    
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (primes[i]) {
            for (let j = i * i; j <= n; j += i) {
                primes[j] = false;         // Mark factors non-prime
            }
        }
    }
    
    return primes.reduce((acc, isPrime, index) => {
        if (isPrime) acc.push(index);
        return acc;
    }, []);
}

Pierwiastek kwadratowy z 30 to 5 z groszami. Czyli wychodzi na to, że aby podać liczby w zakresie od 2 do 30 (pierwsze) wystarczy skreślić te podzielne przez 2,3,4 i 5. Możemy to sprawdzić, czy kiedyś skreślaliśmy jakieś następne liczby.

Zobaczmy, że na przykład kwadratowy z 36 to jest 6, ale do skreślenia 36 wystarczy już nam 3… Jakaś matematyka się za tym kryje, ale programista nie jest matematykiem (to znaczy nie musi być).

Programista pisze, sprawdza czy optymalne, szuka optymalizacji, przygotowuje test-case’y i sprawdza, wreszcie programista może się zastanowić czy porównywanie int i float (liczba z groszami po pierwiastkowaniu) jest super optymalne czy nie.

Oraz czy takie porównywanie int i float jest w ogóle mądre a nawet czy jest w jego języku możliwe. Wtedy warto rzucić okiem na jakiś statycznie typowany język, np. cpp jak oni tam podchodzą:


    for (int p = 2; p * p <= n; p++) {
        
        if (prime[p] == true) {
            
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }

No jak widać można dać warunek 6 * 6 <=36 zamiast 6 <= Math.sqrt(36). A dziwnego porównywania floata z intem unikamy, nawet jeśli nie do końca ogarniamy jak tam te floaty i inty są w JavaScript trzymane (niby jeden typ Number, ale parseInt i parseFloat to osobne funkcje).

JS – sito eratostenesa