Узнайте об эффективном алгоритме определения, является ли заданное число простым или нет. Также узнайте, как реализовать алгоритм простого числа в программе Java 8.
1. Простое число
Простое число — это натуральное число больше 1, которое не может быть образовано путем умножения двух меньших натуральных чисел, отличных от 1.
Другими словами, простое число(P) — это число больше 1, единственными множителями которого являются 1 и само число(P).
Например, 3 является простым числом, потому что его можно разделить только на 1 и 3(само по себе). Однако 4 НЕ является простым числом, потому что его можно разделить на 2, т.е. его можно записать как 2 x 2.
Существует бесконечно много простых чисел. Другими словами, последовательность простых чисел «2, 3, 5, 7, 11, 13, …» никогда не заканчивается.
2. Алгоритм вычисления простого числа
Обратите внимание, что не существует эффективной формулы(доказанной математически), позволяющей определить, является ли число простым или нет.
Как правило, мы можем определить, является ли число простым или нет, выполнив следующие шаги:
- 2 — это простое число, которое также является четным числом. Таким образом, если заданное число N равно 2, то оно является ПРОСТЫМ числом.
- Если заданное число N является четным, то оно НЕ является ПРОСТЫМ числом.
- Найдите квадратный корень из N. Пройдитесь по всем нечетным числам до sqrt(N) и попробуйте разделить N на текущее нечетное число. Если остаток равен 0 для любого нечетного числа, то число НЕ ПРОСТОЕ.
- В противном случае – число ПРОСТОЕ.
boolean isPrime(int number){if(number <= 2)return number == 2;elsereturn (number % 2) != 0&&IntStream.rangeClosed(3,(int) Math.sqrt(number)).filter(n -> n % 2 != 0).noneMatch(n ->(number % n == 0));}3. Программа Java для определения простого числа
Давайте реализуем приведенный выше алгоритм поиска простых чисел в Java 8. Мы использовали IntStream, который помогает генерировать последовательность целых чисел, поддерживая последовательные и параллельные агрегатные операции.
package com.howtodoinjava.example;import java.util.stream.IntStream;public class Main{public static void main(String[] args){System.out.println("2 is prime number :: " + isPrime(2));System.out.println("3 is prime number :: " + isPrime(3));System.out.println("4 is prime number :: " + isPrime(4));System.out.println("5 is prime number :: " + isPrime(5));System.out.println("6 is prime number :: " + isPrime(6));System.out.println("7 is prime number :: " + isPrime(7));System.out.println("8 is prime number :: " + isPrime(8));System.out.println("9 is prime number :: " + isPrime(9));System.out.println("10 is prime number :: " + isPrime(10));System.out.println("11 is prime number :: " + isPrime(11));}static boolean isPrime(int number) {if(number <= 2)return number == 2;elsereturn (number % 2) != 0&&IntStream.rangeClosed(3,(int) Math.sqrt(number)).filter(n -> n % 2 != 0).noneMatch(n ->(number % n == 0));}}Вывод программы.
2 is prime number :: true3 is prime number :: true4 is prime number :: false5 is prime number :: true6 is prime number :: false7 is prime number :: true8 is prime number :: false9 is prime number :: false10 is prime number :: false11 is prime number :: true
Напишите мне ваши вопросы, связанные с тем, как определить, является ли заданное число простым в Java.
Ссылки: