Проверете дали числото е първостепенно в Java

1. Въведение

Първо, нека да разгледаме някои основни теории.

Най-просто казано, числото е просто, ако се дели само на едно и на самото число. Непростите числа се наричат ​​съставни числа. А номер едно не е нито прост, нито композитен.

В тази статия ще разгледаме различни начини за проверка на първичността на число в Java.

2. Персонализирана реализация

С този подход можем да проверим дали число между 2 и (квадратен корен от числото) може точно да раздели числото.

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

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 използва това, което е известно като тестовете за първичност „Miller - Rabin and Lucas - Lehmer“, за да провери дали числото вероятно е първостепенно. В случаите, когато числото е по-малко от 100 бита, се използва само тестът „Милър - Рабин“, в противен случай и двата теста се използват за проверка на първичността на число.

Тестът „Miller-Rabin“ повтаря фиксиран брой пъти, за да се определи първоначалността на числото и този брой итерации се определя чрез проста проверка, която включва битовата дължина на числото и стойността на сигурността, предадени на API:

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

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

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

Първо, трябва да импортираме библиотеката на Apache Commons Math, като добавим следната зависимост в нашия pom.xml :

 org.apache.commons commons-math3 3.6.1 

Най-новата версия на commons-math3 можете да намерите тук.

Можем да направим проверката само като извикаме метода:

Primes.isPrime(number);

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

В това бързо писане видяхме три начина за проверка за първостепенността на числото.

Кодът за това може да бъде намерен в пакета com.baeldung.algorithms.primechecker над на Github.