Решето Ератосфена — метод пошуку простих чисел

Як ми вже встигли переконатись, не всі числа важко ідентифікувати як прості або складені. Наприклад, будь-яке парне число більше 2 є складеним. Однак, хоча деякі числа можуть бути легко класифіковані, для інших дана процедура може бути надзвичайно складною. На щастя, є деякі прийоми, які дозволяють значно спростити процес відшукання простих чисел. Одним з таких прийомів є сито Ератосфена — математичний інструмент, який використовується для виявлення всіх можливих простих чисел між будь-якими двома числами. Метою цього параграфу є максимально ефективна реалізація даного алгоритму засобами Java, не вдаючись до імпорту будь-яких стандартних бібліотек.

Виходячи з того, що пошук, в даному випадку, завжди буде починатись з двійки, то для здійснення задуманого, від користувача, нам знадобиться лише кінець діапазону. Отже, на першому кроці, реалізуємо процес його введення.

// Програма для генерації простих чисел використовуючи решето Ератосфена
import java.util.Scanner;
class Sieve_of_eratosthenes {
public static void main (String args[]) {
Scanner scann = new Scanner(System.in);
// Ввід кінця діапазону
System.out.print("Enter end of range: ");
int end = scann.nextInt();

Далі, оголошуємо та виділяємо пам'ять під масив з числами цілого типу і, простим присвоюванням в циклі (починаючи з двійки і закінчуючи кінцем діапазону) виконуємо запис значень в його комірки.

Читати повністю