Определение простых чисел в JavaScript

Определение того, является ли число простым или нет, является одной из базовых задач в математике и программировании.

Простые числа - это натуральные числа больше 1, которые имеют ровно два делителя: 1 и само число.

Перебор делителей

Один из простых способов определить, является ли число простым или нет, - это перебрать все возможные делители числа и проверить их. Если у числа есть делитель, отличный от 1 и самого числа, то оно не является простым.

function isPrime(num) {
    if (num <= 1) {
        return false;
    }
    for (let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i === 0) {
            return false;
        }
    }
    return true;
}

// Пример использования:
console.log(isPrime(2));   // true
console.log(isPrime(992)); // false

Этот метод эффективен, когда нужно определить простоту небольших чисел.

Решето Эратосфена

Решето Эратосфена - это алгоритм, который приписывают древнегреческому математику Эратосфену Киренскому, и который позволяет найти все простые числа в заданном диапазоне. Метод Решето Эратосфена основан на идее исключения кратных чисел.

function sieveOfEratosthenes(max) {
    let sieve = [];
    let primes = [];
    for (let i = 2; i <= max; i++) {
        if (!sieve[i]) {
            primes.push(i);
            for (let j = i * 2; j <= max; j += i) {
                sieve[j] = true;
            }
        }
    }
    return primes;
}

// Пример использования:
console.log(sieveOfEratosthenes(30)); [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Этот метод эффективен для поиска всех простых чисел в большом диапазоне.