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

Вернуться назад

7 мая 2019

Простое число - это число, которое делится нацело без остатка только на 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 (int 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 (int i = 0; i < primes.size(); i++) {
        int prime = primes.get(i);
        if (prime > sqrt) {
            return true;
        }
        if (n % prime == 0) {
            return false;
        }
    }
    return true;
}

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

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

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

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

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

Последняя оптимизация оказалась наиболее существенной.

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



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

Ваше имя:
Текст комментария: