Перейти к основному содержимому

Проверить, является ли число простым в Java

· 2 мин. чтения

1. Введение​

Во-первых, давайте рассмотрим некоторые основные теории.

Проще говоря, число является простым, если оно делится только на единицу и на само число. Непростые числа называются составными числами. И число один не является ни простым, ни составным.

В этой статье мы рассмотрим различные способы проверки простоты числа в Java.

2. Пользовательская реализация​

При таком подходе мы можем проверить, может ли число от 2 до (квадратный корень из числа) точно разделить число.

Следующая логика вернет true , если число простое:

public boolean isPrime(int number) {
    return number > 1 
      && IntStream.rangeClosed(2, (int) Math.sqrt(number))
      .noneMatch(n -> (number % n == 0));
}

3. Использование BigInteger​

Класс BigInteger обычно используется для хранения целых чисел большого размера, то есть тех, которые больше 64 бит. Он предоставляет несколько полезных API для работы со значениями типа int и long .

Одним из таких API является isProbablePrime . Этот API возвращает false , если число определенно является составным, и возвращает true , если существует некоторая вероятность того, что оно простое. Это полезно при работе с большими целыми числами, потому что их полная проверка может потребовать довольно интенсивных вычислений.

Небольшое примечание : API isProbablePrime использует так называемые тесты простоты «Миллера — Рабина и Лукаса — Лемера», чтобы проверить, является ли число, вероятно, простым. В случаях, когда число меньше 100 бит, используется только критерий «Миллера — Рабина», в противном случае для проверки простоты числа используются оба критерия.

Тест «Миллера-Рабина» выполняет фиксированное количество итераций для определения простоты числа, и это количество итераций определяется простой проверкой, которая включает в себя длину числа в битах и значение достоверности, передаваемое в API:

public boolean isPrime(int number) {
    BigInteger bigInt = BigInteger.valueOf(number);
    return bigInt.isProbablePrime(100);
}

4. Использование математики Apache Commons​

Apache Commons Math API предоставляет метод с именем org.apache.commons.math3.primes.Primes, который мы будем использовать для проверки простоты числа.

Во-первых, нам нужно импортировать математическую библиотеку Apache Commons, добавив следующую зависимость в наш pom.xml :

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.6.1</version>
</dependency>

Последнюю версию commons-math3 можно найти здесь .

Мы могли бы сделать проверку, просто вызвав метод:

Primes.isPrime(number);

5. Вывод​

В этом кратком обзоре мы рассмотрели три способа проверки простоты числа.

Код для этого можно найти в пакете com.foreach.algorithms.primechecker на Github.