Автор оригинала: Pankaj Kumar.
Что такое Простое число?
Простое число-это натуральное число, большее 1, которое делится только на 1 и само по себе.
Например, 5-простое число, потому что его можно разделить только на 1 и 5.
Аналогично, 6 не является простым числом, потому что его можно разделить на 1, 2, 3 и 6.
Алгоритм поиска простых чисел от 1 до N
Существует множество алгоритмов для нахождения простого числа в заданном диапазоне. “Сито Эратосфена” – один из популярных и простых алгоритмов поиска простых чисел с точностью до заданного диапазона.
Алгоритм поиска простых чисел от 1 до N состоит из следующих шагов.
- Создайте список последовательных чисел от 2 до N, т. е. (2,3,4…N).
- Начните с первого и наименьшего простого числа 2. Допустим, переменная.
- Найдите кратные p, т. е. 2p, 3p, 4p, и отметьте их в списке как не простые числа. Обратите внимание, что число p не должно быть помечено само по себе.
- Найдите следующий номер в списке, который не отмечен, и выполните с ним предыдущий шаг.
- Когда числа в списке исчерпаны, алгоритм завершается. Список чисел, которые не помечены, – это простые числа от 1 до N.
Ниже GIF дает визуальное представление алгоритма (Источник: Википедия ).
Сито Алгоритма Эратосфена
Реализация Java для поиска простых чисел от 1 до N
package com.journaldev.examples;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PrimeNumbers {
public static void main(String[] args) {
System.out.println(findPrimeNumbers(100));
}
// generating the list of prime numbers from 2 to the given number
// using the Sieve of Eratosthenes algorithm
private static List findPrimeNumbers(int n) {
// initialize the array with "true", index denotes the numbers from 0 to n.
boolean[] primes = new boolean[n + 1];
Arrays.fill(primes, true);
//loop from 2 to x until x*x becomes greater than n
for (int i = 2; i * i < n; i++) {
// process if the number is not already marked
if (primes[i]) {
// find the multiples and mark them as false
for (int j = i * i; j <= n; j += i)
primes[j] = false;
}
}
// populate the list of prime numbers from the array and return it
List primeNumbers = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (primes[i])
primeNumbers.add(i);
}
return primeNumbers;
}
}
Выход : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Алгоритм проверки того, является ли число простым?
Самый простой способ проверить, является ли число простым, – это использовать пробное деление.
Для данного числа N проверьте, существует ли простое число M от 2 до √N (квадратный корень), которое равномерно делит его, т. е. Остаток равен 0.
Если существует число M, которое равномерно делит N, то N не является простым числом. В противном случае N-простое число.
Реализация Java для проверки простого числа
Вот реализация, позволяющая проверить, является ли число простым или нет. Мы будем использовать ранее определенный метод, чтобы узнать простые числа от 2 до √N.
package com.journaldev.examples;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PrimeNumbers {
public static void main(String[] args) {
int number = 123456789;
boolean isPrime = checkPrime(number);
System.out.printf("%d is Prime: %b.\n", number, isPrime);
System.out.printf("%d is Prime: %b.\n", 3511, checkPrime(3511));
System.out.printf("%d is Prime: %b.\n", 123, checkPrime(123));
}
// a number is not prime if there is a prime number between 2 to the square root of
// num that evenly divides it
private static boolean checkPrime(int num) {
// get the prime numbers from 2 to square root of num.
List primes = findPrimeNumbers(Double.valueOf(Math.sqrt(num)).intValue());
System.out.println(primes);
for (int i : primes) {
if (num % i == 0) {
System.out.printf("%d is divided by %d.\n", num, i);
return false;
}
}
return true;
}
}