Как определить простое число java

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

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

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

public List getFirstPrimes( int count) List 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 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 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 первых простых чисел. Если же вы ищете все простые числа в некотором диапазоне, то лучше использовать Решето Эратосфена для поиска простых чисел – он будет работать гораздо быстрее.

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

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

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

В этой статье мы рассмотрим различные способы проверки простоты числа в 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.commonsgroupId>   artifactId>commons-math3artifactId>   version>3.6.1version>   dependency> 

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

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

 Primes.isPrime(number); 

5. Вывод​

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

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

Java для школьников. Занятие №9. Интересная задача. Проверка — является ли число простым?

Можно сказать, мы потратили на изучение Java уже достаточно времени и вполне можем решать уже какие-либо интересные задачи. К одной из таких задач можно отнести, например, проверку — является ли введенное число простым? О простых числах и об алгоритмах нахождения простых чисел можно почитать здесь. Для тех, кто не хочет углубляться в теорию, скажем, что простое число, это натуральное число (т.е. употребляемое для счета предметов), которое делится на единицу и на самого себя.

На этом занятии мы разберем несколько важных аспектов программирования на Java:

• Метод main() и точка входа в программу;
• организация ввода данных с помощью аргументов программы в командной строке (здесь также вспомним про строковый и другие типы данных);
• операторы цикла;
• операторы сравнения в Java.

плюс — некоторые операторы, которые часто применяются программистами в работе:

• нахождение остатка от деления;
• оператор return и завершение программы.

Листинг 1. Проверка — является ли число простым (файл IsNumberIsSimple.java)

public class IsNumberIsSimple

public static void main ( String args [ ] ) <
int num = Integer . parseInt ( args [ 0 ] ) ;

for ( int i = 2 ; i < num ; i ++ ) <
if ( num % i == 0 ) <
System . out . println ( «This number is not simple. » ) ;
return ;
>
>
System . out . println ( «Very well! It’s simple!» ) ;
>
>

Чтобы убедиться, что программа работает, необходимо скомпилировать ее командой
javac IsNumberIsSimple.java
и, внимание, запустить с аргументом — числом для проверки, например
java IsNumberIsSimple 7

Аргумент программы — это параметр, который в командной строке пишется после имени программы через пробел.

О компиляции и запуске программ на языке Java см. Занятие 3.

Давайте теперь разберем подробнее программу из Листинга 1. Нужно сказать, что она получилась достаточно компактной. В классе IsNumberIsSimple использован всего лишь один метод main(), и, думается, настало время поговорить об этом методе более подробно. Во многих языках программирования имеется метод (функция), определяющий так называемую «точку входа» в программу. Язык Java многое позаимствовал от языков C/C++, в том числе и название такой точки входа. Речь идет о том, что если Вы хотите, чтобы программа была выполнена операционной системой ( в нашем случае виртуальной машиной), необходимо снабдить ее исходный код методом main(). Для языка программирования Java это означает, что необходимо включить метод main() в основной класс программного модуля. (Если в этом абзаце ничего не понятно, см. Занятие 1, Занятие 8 или просто поверьте что код Листинга 1 будет работать, а ознакомление с этими понятиями оставьте «на потОм»).

Мы пока сознательно опустим объяснение что такое статический метод, но обязательно вернемся к этому позже. Далее, оказывается, в метод main() можно передавать параметры, как сказано выше — массив строк. (О передаче параметров в метод см. в материале Занятия №6). До этого мы уже были знакомы со строками, т.к. выводили сообщения с помощью метода println() класса System. Строковый тип данных используется в программировании постоянно. И представляет из себя последовательность символов обычно состоящую из букв, знаков препинания и цифр. Вспомните незабываемый фрагмент кода из Занятия №4:

System . out . println ( «Да здравствует Java. » ) ;

Фраза, заключенная в кавычки — «Да здравствует Java. » — типичный представитель строкового типа данных.

Далее, еще один новый термин — массив. Массив — это упорядоченный набор данных, идентифицируемых с помощью индексов. В простейшем случае массив имеет постоянную длину и хранит единицы данных одного и того же типа (подробнее см., например, в Википедии). В нашем случае, в метод main() передается массив строк под названием args. Что интересно, первый из элементов массива будет иметь индекс 0. Т.е. в ячейке памяти, отведенной под переменную с именем args[0] будет храниться первый и единственный параметр командной строки для нашей программы. Это и будет число для проверки (вспомните цель нашей программы — проверить является ли какое-то число простым).

В программе мы объявили всего лишь одну переменную:

int num = Integer . parseInt ( args [ 0 ] ) ;

тип этой переменной — int. Так в Java объявляются целочисленные переменные. Что такое целое число? Математическое определение целых чисел можно посмотреть здесь. Как видно, ряд натуральных чисел входит в состав целых. Так для чего нам понадобилась такая целочисленная переменная? Как уже было сказано, в метод main() передается строковый массив, а в первом его элементе — args[0] хранится первый параметр метода main() (число для проверки), который тоже является строкой, но со строками в программировании, к сожалению, нельзя выполнять математических операций, а они (точнее некоторые из них) нам обязательно понадобятся.

С помощью конструкции

Integer . parseInt ( args [ 0 ] ) ;

мы преобразовали первый элемент строкового массива args к типу целочисленных переменных.

Идея нашей программы проста. Если ввести в программу в качестве аргумента число больше 2, программа будет перебирать все целые числа и проверять делится число, которое мы ввели на текущее. Перебор всех целых чисел, которые меньше аргумента нашей программы, достигается при помощи следующей конструкции (оператора) for:

for ( int i = 2 ; i < num ; i ++ ) < . >

В которой внутри круглых скобок код символом «;» разделен на три части — в первой определяется переменная i, уже знакомого нам целочисленного типа, и ей сразу же присваивается значение 2, во второй записывается условие, до выполнения которого будет выполняться третья часть оператора for — в нашем случае это увеличение переменной i на единицу. Увеличение переменной на единицу записывается с помощью еще одного «хитрого» оператора ++. Итак, пока условие, записанное во второй части кода в круглых скобках, не сработало, будет выполняться блок кода, заключенный в фигурные скобки. Такая конструкция в программировании называется циклом, а оператор for называется «оператором цикла».

Далее, в теле цикла for (в блоке кода, заключенного в фигурные скобки) с помощью оператора if, осуществляющего проверку условия

if ( num % i == 0 ) <
System . out . println ( «This number is not simple. » ) ;
return ;
>

мы проверяем, делится ли исходное число (аргумент нашей программы — попавший в переменную num после присваивания) на текущее (переменная i) нацело (т.е. без остатка) с помощью оператора выделения остатка от деления «%». И, если делится, это означает что число не является простым, Далее программа прерывает свое выполнение с помощью оператора return. В данном случае оператор return вернет управление среде, вызвавшей метод main(), т.е. виртуальной машине Java и операционной системе.

Если же, перебрав все целые числа от 2 до num в цикле for мы не обнаружили ни одного случая деления без остатка, то, по определению, аргумент программы — целое число.

Задание для самостоятельного выполнения:
* доработайте программу так, чтобы она проверяла введенное число на условие «является ли оно составным?». Узнайте что такое составное число.

1. И.Хабибуллин «Java 2», с.91

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

Как определить простое число в Java

Очень важный вопрос в математике и безопасности говорит о том, является ли число простым или нет. Это очень полезно при шифровании пароля. В этом уроке вы узнаете, как найти простое число в простых случаях.

Тривиальные Случаи

Мы узнали, что числа простые, если у них есть только делители 1 и сам. Тривиально, мы можем проверить каждое целое число от 1 до самого себя (эксклюзивно) и проверить, делится ли оно равномерно.

Например, может возникнуть соблазн запустить этот алгоритм:

 // проверяет, является ли int простым или нет. boolean isPrime(int n) < for(int i=2;ireturn true; > 

Сначала это не кажется плохим, но мы можем сделать это быстрее — намного быстрее. Предположим, что если 2 делит некоторое целое число n, то (n / 2) также делит n. Это говорит нам о том, что нам не нужно пробовать все целые числа от 2 до n. Теперь мы можем изменить наш алгоритм:

 // проверяет, является ли int простым или нет. boolean isPrime(int n) < for(int i=2;2*ireturn true; > 

При более эффективном кодировании мы замечаем, что вам действительно нужно перейти только к квадратному корню из n, потому что если вы перечислите все факторы числа, квадратный корень всегда будет посередине (если это произойдет не быть целым числом, мы все еще в порядке, мы могли бы быть слишком приблизительными, но наш код все еще будет работать).

Наконец, мы знаем, что 2 — это «самое странное» простое число — оно оказывается единственным четным простым числом. Из-за этого нам нужно только проверить 2 отдельно, затем пройти нечетные числа до квадратного корня из n. В итоге наш код будет выглядеть так:

 // проверяет, является ли int простым или нет. boolean isPrime(int n) < // проверяем, является ли n кратным 2 if (n%2==0) return false; // если нет, тогда просто проверьте шансы for(int i=3;i*i<=n;i+=2) < if(n%i==0) return false; >return true; > 

Как вы можете видеть, мы прошли путь от проверки каждого целого числа (до n, чтобы узнать, что число простое) до простой проверки половины целых чисел вплоть до квадратного корня (на самом деле, нечетных). Это огромное улучшение, особенно если учесть большие цифры.

Повторы

Допустим, вы пишете программу, в которой вас просят проверить, много ли чисел простое; не один раз Хотя наша программа, приведенная выше, оптимизирована для этого алгоритма, существует другой способ, специально подходящий для этой ситуации: Prime Sieve.

ЧИТАТЬ ТАКЖЕ: Невозможно найти Spring NamespaceHandler для пространства имен схемы XML [http://jax-ws.dev.java.net/spring/servlet]

Вот основная идея:

1. Предположим, что каждое целое число, большее или равное 2, простое.
2. Начните с начала списка, если число простое, вычеркните все множители этого числа из списка. Они не простые.
3. Переходите к следующему числу, если оно вычеркнуто, пропустите его — оно не простое. Если оно не вычеркнуто, оно должно быть простым, вычеркните его кратные.
4. Повторение

Посмотрим, что это значит. Рассмотрим список:

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 . 

2 простое . вычеркните это кратно. Наш список теперь выглядит так:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .

Вы можете понять, почему 2 — единственное простое число. Делая это с помощью 3, мы вычеркиваем 6 (уже вычеркнуто), 9, 12 (уже вычеркнуто), 15 и т. Д. В конце концов, ваш список будет выглядеть так:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .

А наши простые числа остались: (2,3,5,7,11,13,17,19,23,29, . ). В коде вы можете отслеживать этот список как массив. Это означает, что вы настроите «сито» через n чисел, но восполните его при повторном вызове функции, так как она вернет мгновенное значение, является ли число простым или нет. Вот как это будет выглядеть. Конечно, вы можете отредактировать это самостоятельно в соответствии со своими потребностями:

 import java.util.Arrays; // глобальный массив, чтобы отслеживать его в этом примере, // но вы можете легко сделать это в другой функции. // будет содержать значения true или false для первых 10000 целых чисел boolean[] primes=new boolean[10000]; // настройка простого числа public void fillSieve() < Arrays.fill(primes,true); // предположим, что все целые числа простые. primes[0]=primes[1]=false; // мы знаем, что 0 и 1 не простые. for (int i=2;i> > > public boolean isPrime(int n) < return primes[n]; // просто, а? >