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

Как найти простые числа в java

  • автор:

Проверить, является ли число простым в 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 Поиск простых чисел

Вопрос: Зачем использовать второй цикл и каждый раз заходить в него? почему сразу не сделать в первом цикле проверку i%2? т.е.:

for(int i = 2; i if(isPrime) < System.out.println(i); >> 

Отслеживать
задан 10 дек 2020 в 5:42
Антон Алексеевич Антон Алексеевич
57 1 1 серебряный знак 6 6 бронзовых знаков
Видимо, Вы путаете простые числа с нечётными
Commented 10 дек 2020 в 6:10

Просто́е число́ — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя[1]. Другими словами, число x является простым, если оно больше 1 и при этом делится без остатка только на 1 и на x. К примеру, 5 — простое число, а 6 не является простым числом, так как, помимо 1 и 6, оно также делится на 2 и на 3.

Commented 10 дек 2020 в 6:17
если заменить for(int j = 2; j < i; j++)< if(i % j == 0)< isPrime = false; break; >> то в вашем случае вы не определите простое ли оно
Commented 10 дек 2020 в 6:19

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Простые числа это те которые нацело делятся только на 1 и на само себя.

Например 2 — это простое число, т.к. оно делится на 1 и на 2. А вот 6 делится на 1, 2, 3, 6 и является составным.

Поэтому второй цикл необходим всего лишь для того чтобы пробежаться по всем делителям числа.

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

Возьмем число 16. У него есть следующие делители:

После 4 все делители как будто бы отзеркаливаются. Это происходит после квадратного корня. Но так как квадратный корень это нечто дробное, то желательно округлить его и прибавить 1 или 2, чтобы точно быть уверенным что вы не пропустили, например делитель 7 в числе 49.

Полный код программы такой:

for (int n = 2; n System.out.print(isPrime ? (n + " ") : ""); > 

Помогите вывести простые числа в java

Помогите составить программу в JAVA которая принимает целое число, выводит на экран все простые числа от нуля до принятого числа. Используя только простые операции if и for Я составил, но что-то не помогает import java.util.Scanner;

public class prostue_chisla < public static void main(String[] args) < System.out.println("Введите положительное число: "); Scanner in = new Scanner(System.in); int input = in.nextInt(); boolean b = true; for (int P = 1; P System.out.println(P);> > > > 

Отслеживать
задан 10 ноя 2017 в 19:34
59 1 1 золотой знак 2 2 серебряных знака 9 9 бронзовых знаков
Зачем вам переменная b ? Что конкретно в приведённом коде работает неправильно?
Commented 10 ноя 2017 в 19:45
Вот что оно выдает:Введите положительное число: 5 2 3 3 4 4 4 5 5 5 5
Commented 10 ноя 2017 в 20:44

7 ответов 7

Сортировка: Сброс на вариант по умолчанию

Если используете java 8+ , лучше юзать в вашем случае IntStream для целых чисел:

public static boolean isPrime(final int number) < return IntStream.rangeClosed(2, number / 2).anyMatch(i ->number % i == 0); > 
System.out.println(isPrime(1)); // false System.out.println(isPrime(2)); // true 

Отслеживать
ответ дан 23 мая 2018 в 6:28
4,117 4 4 золотых знака 14 14 серебряных знаков 29 29 бронзовых знаков

public static void main(String[] args) < Scanner scanner = new Scanner(System.in); int top = scanner.nextInt(); for (int i=2;i> public static boolean checkSimple(int i) < if (i<=1) return false; else if (i <=3) return true; else if (i%2==0 || i %3 ==0) return false; int n = 5; while (n*n <=i)< if (i % n ==0 || i % (n+2) == 0) return false; n=n+6; >return true; > 

Алгоритм проверки на то, что число является простым взял отсюда : https://en.wikipedia.org/wiki/Primality_test

Отслеживать
ответ дан 10 ноя 2017 в 19:49
aleshka-batman aleshka-batman
2,888 10 10 серебряных знаков 21 21 бронзовый знак
Что-то все равно не выходит
Commented 10 ноя 2017 в 20:42

Проблема не со сканером, а с алгоритмом. Во-первых, он не оптимален, во-вторых, содержит ошибку. Но, если вы хотите искать простые числа именно таким способом, исправьте свой метод таким образом

public static void main(String[] args) < System.out.println("Введите положительное число: "); Scanner in = new Scanner(System.in); int input = in.nextInt(); boolean b = true; for (int P = 2; P > if (b) System.out.println(P); else b = true; > > 

Отслеживать
ответ дан 10 ноя 2017 в 20:32
10.3k 2 2 золотых знака 11 11 серебряных знаков 26 26 бронзовых знаков
Вот что выдает: Введите положительное число: 5 2 3 3 4 4 4 5 5 5 5
Commented 10 ноя 2017 в 20:46
может вы что-то неправильно скопировали, потому как у меня выдает 5 1 2 3 5
Commented 10 ноя 2017 в 20:48
1 — не простое.
Commented 10 ноя 2017 в 20:50
Спасибо, но все скопировал правильно
Commented 10 ноя 2017 в 20:52
меняем р=1 на р=2 и все хорошо, 1 не выводится
Commented 10 ноя 2017 в 20:52

//variable 'input' is input numeric for (int i = 2; i > if (rez != null) < System.out.println(rez); >> 

Отслеживать
ответ дан 23 мая 2018 в 5:48
JavaJunior JavaJunior
1,538 7 7 серебряных знаков 17 17 бронзовых знаков

Программа проверяет, числа от 11 и до бесконечности, и выводит количество простых чисел на экран + все простые числа + время работы программы. При желании можно отключить массив и выводить только количество простых чисел, что ускорит время работы программы процентов на 30. Без проблем можно запилить еще один метод, для проверки и вывода чисел до 10 и при помощи if проверять n

public class reshenie < public static void main(String[] args) < int count = 4;//начинаем с 4, т.к. до 10 нам известны все простые числа и программа их не обрабатывает. int n = 100000;//число до которого необходимо найти все простые числа ArrayListnumbers = new ArrayList<>();//создаем массив, необходим для вывода чисел на экран, можно и без массива, просто выводить каждое найденное простое число numbers.add(2);//добавляем в массив простые числа до 10(см count = 4) numbers.add(3); numbers.add(5); numbers.add(7); Date startTime = new Date();//время старта for (int i = 11; i  > Date finishTime = new Date();//время окончания работы алгоритма long ct = finishTime.getTime() - startTime.getTime();//время работы System.out.println("Время вычислений: " + ct + "ms");//вывод на экран времени работы System.out.println("Количество простых чисел: " + count);//вывод количества System.out.print(numbers);//вывод всех чисел > static boolean simple(int a) else < for (int j = 3; j  > > if (p > 0) else return true; > > 

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

Нужно написать программу, которая при вводе числа с клавиатуры определяет простое оно или нет. Я не могу понять, как записать сравнение со всеми простыми числами.

Отслеживать
34.2k 25 25 золотых знаков 131 131 серебряный знак 225 225 бронзовых знаков
задан 15 окт 2016 в 13:42
85 1 1 золотой знак 1 1 серебряный знак 9 9 бронзовых знаков
Надо просто перебрать все простые числа от нуля до sqrt(N) и при делении нацело прерывать процесс.
Commented 15 окт 2016 в 13:51
Вам нужно реализовать один из т.н. «тестов простоты», например вероятностный тест Рабина-Миллера.
Commented 15 окт 2016 в 14:01

@ВладимирМартьянов если ему не нужна быстродейственность и не такие уж и большие числа, то самый простой тест Ферма. А так тестов на простоту достаточно, сам лично знаю штук 5.

Commented 15 окт 2016 в 16:18
@ParanoidPanda, Рабин-Миллер прост, интересен и скорее всего более чем достаточен 🙂
Commented 15 окт 2016 в 16:19

4 ответа 4

Сортировка: Сброс на вариант по умолчанию

Чтобы определить простоту не надо сравнивать со всеми простыми числами, достаточно выполнить тест простоты. В Java уже реализован тест Рабина-Миллера в классe BigInteger .

Integer integer = 12311; BigInteger bigInteger = BigInteger.valueOf(integer); boolean probablePrime = bigInteger.isProbablePrime((int) Math.log(integer)); System.out.println(probablePrime); 

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

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