Статьи
Утилиты Telegram YouTube Отзывы

Алгоритм поиска простых чисел

Видеогайд

16 июня 2022

Тэги: Java, алгоритмы.

Простое число – это число, которое делится нацело без остатка только на 1 и на самого себя. Также известно, что любое целое число, большее 1, является либо простым, либо может быть выражено как произведение простых чисел. Ряд простых чисел начинается с 2 и имеет следующий вид: 2, 3, 5, 7 и т.д.

Рассмотрим алгоритм поиска простых чисел, известный как «метод перебора делителей». Для этого давайте реализуем на Java метод getFirstPrimes(), который будет возвращать N первых простых чисел.

public List<Integer> getFirstPrimes(int count) {
    List<Integer> primes = new ArrayList<>();
    if (count > 0) {
        primes.add(2);
    }
    for (var i = 3; primes.size() < count; i += 2) {
        if (isPrime(i, primes)) {
            primes.add(i);
        }
    }
    return primes;
}

Все найденные простые числа будем складывать в список. Далее проверяем, что если у нас запросили хотя бы одно простое число, то сразу добавим 2, т.к. с него начинается последовательность. Далее в цикле начинаем проверять числа, сразу начиная с трёх. Также обратите внимание, что мы проверяем только нечётные числа (приращение +2), т.к. все чётные числа по определению делятся на 2.

Цикл выполняется до тех пор, пока в нашем результирующем списке не окажется ровно столько простых чисел, сколько у нас запросили. Саму проверку на «простоту» выполняем с помощью метода isPrime(), которому передаём текущее проверяемое число и уже накопленные нами на предыдущих итерациях числа.

private boolean isPrime(int n, List<Integer> primes) {
    double sqrt = Math.sqrt(n);
    for (var i = 0; i < primes.size(); i++) {
        var prime = primes.get(i);
        if (prime > sqrt) {
            return true;
        }
        if (n % prime == 0) {
            return false;
        }
    }
    return true;
}

Здесь мы сначала вызываем метод Math.sqrt(), ведь если проверяемое число состоит хотя бы из двух множителей, то ни одно из них не может превышать двоичный корень.

Затем в цикле проходим по всем уже найденным простым числам и по очереди пытаемся делить на них текущее число. Если число делится на простое число без остатка – значит, оно составное. Проверку выполняем до тех пор, пока простые числа меньше корня из проверяемого числа.

Можно выполнить небольшую оптимизацию, отказавшись от вычисления квадратного корня и операций над типом double. Вместо этого будем возводить каждое уже найденное простое число в квадрат и проверять, не превысило ли это произведение потенциально простое число. Если превысило, значит, перед нами новое простое число:

private boolean isPrime(int n, List<Integer> primes) {
    for (var i = 0; i < primes.size(); i++) {
        var prime = primes.get(i);
        if (prime * prime > n) {
            return true;
        }
        if (n % prime == 0) {
            return false;
        }
    }
    return true;
}

Рассмотренный алгоритм работает довольно быстро. За пару секунд он находит 500 000 простых чисел.

Оптимизации, которые мы применили:

  • проверяем только нечётные числа
  • пытаемся делить только на уже найденные простые числа
  • делителями могут быть только те простые числа, которые не превосходят квадратного корня из проверяемого числа
  • вместо вычисления квадратного корня возводим в квадрат каждое уже найденное простое число, пока произведение не превысит проверяемое число

Данный алгоритм хорошо подходит в том случае, если вам нужно ровно N первых простых чисел. Если же вы ищете все простые числа в некотором диапазоне, то лучше использовать Решето Эратосфена для поиска простых чисел – он будет работать гораздо быстрее.



Комментарии

21.01.2024 12:11 Czech Entropy PRNG

Решето Аткина быстрее

28.01.2024 07:53 1024 bit

Попробую написать и потестировать для больших чисел в 1024 bit. "Готовых" простых чисел для http://shmeleff.com/CzechEntropy.apk не нашел. Похоже их никто не хочет публиковать :-))

Добавить комментарий

×

devmark.ru