JavaScript: jak znaleźć liczby pierwsze (prime numbers)

Zacznijmy od tego co to są liczby pierwsze a później dopiero jak je znaleźć. Liczba pierwsza – liczba naturalna, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą.

W naszym przykładzie wykorzystamy dwie funkcje:

• jedna która sprawdza czy dana liczba jest liczba pierwsza
• oraz drugą która przygotowuje jakiś zbiór tych liczb

Funkcja, która pozwoli sprawdzić czy liczba jest liczbą pierwszą może wyglądać następująco:

function isPrime(num) {
    if(num < 2) return false;
    for (var i = 2; i < num; i++) {
        if(num % i == 0)
            return false;
    }
    return true;
}

Kilka ważnych uwag:

• zakłady, ze każda liczba poniżej 2 nie jest liczba pierwsza
• jeśli liczba `num` nie jest mniejsza niż 2; próbujemy po kolei dzielić ją przez każdą liczbę mniejszą od `num`; np: jeśli `num = 5` to dzielimy przez 3 & 4

Teraz dla przykładu chcemy uzyskać wszystkie liczby pierwsza mniejsze niż 100:

var arr = [];
for(var i = 0; i < 100; i++){
    if(isPrime(i)) { arr.push(i); }
}
console.log(arr);
console.log(arr.length);

Oraz kolejny przykład jak znaleźć 100 pierwszych liczb pierwszych:

var arr = [];
var x = 0;
while(arr.length < 100){
    if(isPrime(x)) { arr.push(x); }
    x++;
}

console.log(arr);
console.log(arr.length)