Java определить простые числа

Как определить простое число в 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.

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]; // просто, а? >

Источник

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

Натуральное число N является простым, если оно отлично от 1 и делится без остатка только на 1 и на само N.

Определить простое число или нет можно следующим методом :

public static boolean isSimple(Integer number)  if(number  2) return false; for(int i = 2; i  number / 2; i++)  if(number % i == 0)  return false; > > return true; > System.out.println(isSimple(97)); // => true System.out.println(isSimple(98)); // => false 

Источник

Проверить, является ли число простым в 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 можно найти здесь .

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

5. Вывод​

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

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

Источник

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

Простое число – это число, которое делится нацело без остатка только на 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

Дан массив произвольных чисел. Проходя по его элементам в цикле, мы будем определять, является ли число простое, и выводить его на экран. Определять это будем с помощью метода isSimple() .

Напомню, что простое число — это натуральное число больше 1, которое делится на 1 и на себя.

Поэтому если число меньше 2, то оно сразу не простое. Затем проверяем, есть ли у числа еще делители, если есть, то оно тоже не простое. Делаем мы это в цикле, при этом делители принимают значения от 2 до квадратного корня от проверяемого числа, т.е. до Math.sqrt(num) . Так как мы гарантированно до значения Math.sqrt(num) либо найдем делитель для нашего числа, либо не найдем.

public class Example  public static void main(String[] args)  int[] arr = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11>; for (int i = 0; i  arr.length; i++)  if (isSimple(arr[i]))  System.out.print(arr[i] + " "); // => 2 3 5 7 11 > > > private static boolean isSimple(int num)  if (num  2)  return false; > for (int k = 2; k  Math.sqrt(num); k++)  if (num % k == 0)  return false; > > return true; > > 

Источник