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

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

  • автор:

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

Дан массив произвольных чисел. Проходя по его элементам в цикле, мы будем определять, является ли число простое, и выводить его на экран. Определять это будем с помощью метода 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; > > 

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

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

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

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

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

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

//checks whether an int is prime or not. boolean isPrime(int n) < for(int i=2;i="">

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

//checks whether an int is prime or not. boolean isPrime(int n) < for(int i=2;2*i="">

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

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

//checks whether an int is prime or not. boolean isPrime(int n) < //check if n is a multiple of 2 if (n%2==0) return false; //if not, then just check the odds for(int i=3;i*i<=n;i+=2) < if(n%i==0) return false; >return true; >

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

Повторения

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

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

  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; //global array just to keep track of it in this example, //but you can easily do this within another function. // will contain true or false values for the first 10,000 integers boolean[] primes=new boolean[10000]; //set up the primesieve public void fillSieve() < Arrays.fill(primes,true); // assume all integers are prime. primes[0]=primes[1]=false; // we know 0 and 1 are not prime. for (int i=2;i="">

Читайте ещё по теме:

  • Самые популярные статьи 2013 года
  • Java – Подсчитывает количество элементов в списке

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *