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

Як ми вже встигли переконатись, не всі числа важко ідентифікувати як прості або складені. Наприклад, будь-яке парне число більше 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();

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

// Оголошення та виділення пам'ять під масив вказаного розміру
int numbers[] = new int[end + 1];
// Заповнення масиву значеннями
for (int i = 1; i <= end; i++) {
numbers[i] = i;
}

На наступному кроці, діємо за алгоритмом Ератосфена, і перш за все відведемо змінну prime під поточне просте число. Спочатку це буде двійка. Далі, викреслюємо з масиву число prime * prime, а потім всі числа, починаючи з цього числа через prime. Звичайно, ми не можемо реально закреслити число в масиві, тому присвоюємо відповідному його елементу значення нуль, яке буде означати, що це число складене. Після цього, шукаємо перше невикреслене число — його значення в масиві має відрізняться від нульового. Тепер змінна prime містить наступне просте число. Якщо prime не перевищує кореня квадратного з максимального числа (в нашому випадку це число end), то продовжуємо ітераційний процеc далі. В іншому випадку всі прості числа в заданому діапазоні вже знайдені, їх значення в масиві — ненульові.

// Викреслюємо в масиві складені числа
int prime = 2;
while (prime <= Math.floor(Math.sqrt(end))) {
int j = prime * prime;
while (j <= end) {
numbers[j] = 0;
j = j + prime;
}
for (int i = prime + 1; i <= end; i++) {
if (numbers[i] != 0) {
prime = i;
break;
}
}
}

Далі, перебираючи весь масив, за вказаною вище ознакою знаходимо прості числа і друкуємо їх на екран.

// Виводимо результати роботи програми
System.out.print(»Prime numbers ranging from 2 to  " + end  + ": «+ numbers[2]);
for (int i = 3; i <= end; i++) {
if (numbers[i] != 0)
System.out.print(»,  " + numbers[i]);
}
System.out.print(";");
}
}

Скомпілювавши, запустивши та задавши в якості кінця діапазону, наприклад, значення 100, на екрані відобразиться наступний результат:

Решето Ератосфена java

Генерація простих чисел використовуючи сито Ератосфена

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар