Рубрики
Без рубрики

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

Узнайте, как проверить первичность числа с помощью Java.

Автор оригинала: baeldung.

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 , если существует некоторая вероятность того, что оно простое. Это полезно при работе с большими целыми числами, потому что для их полной проверки может потребоваться довольно интенсивное вычисление.

Краткое примечание – в isProbablePrime API использует так называемые тесты на примитивность “Миллер – Рабин и Лукас – Лемер”, чтобы проверить, является ли число, вероятно, простым. В тех случаях, когда число меньше 100 бит, используется только тест “Миллер – Рабин”, в противном случае оба теста используются для проверки простоты числа.

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

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

4. Использование Apache Commons Math

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

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


    org.apache.commons
    commons-math3
    3.6.1

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

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

Primes.isPrime(number);

5. Заключение

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

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