Алгоритм сита Ератосфена: Python, C++ Приклад

Автор: Сара Чен Сара Чен
Hours оновлений

Решето Ератосфена - найпростіше решето простих чисел. Це алгоритм простих чисел для пошуку всіх простих чисел у заданому ліміті. Існує кілька сит простих чисел. Наприклад, решето Ератосфена, решето Аткіна, решето Сундарама тощо.

Слово "решето” означає посуд, який фільтрує речовини. Таким чином, алгоритм сита в Python та інших мовах відноситься до алгоритму для фільтрації простих чисел.

Цей алгоритм відфільтровує просте число за допомогою ітераційного підходу. Процес фільтрації починається з найменшого простого числа. Просте число — це натуральне число, яке більше за 1 і має лише два дільники, а саме 1 і саме число. Числа, які не є простими, називаються складеними.

У решеті методу Ератосфена спочатку вибирається маленьке просте число, а всі кратні йому відфільтровуються. Процес виконується в циклі в заданому діапазоні.

Наприклад:

Візьмемо діапазон чисел від 2 до 10.

Алгоритм «Решето Ератосфена».

Після застосування решета Ератосфена воно створить список простих чисел 2, 3, 5, 7

Алгоритм «Решето Ератосфена».

Алгоритм Решето Ератосфена

Ось алгоритм для Решета Ератосфена:

Крок 1) Створіть список чисел від 2 до заданого діапазону n. Ми починаємо з 2, оскільки це найменше і перше просте число.

Крок 2) Виберіть найменше число зі списку, x (спочатку x дорівнює 2), перегляньте список і відфільтруйте відповідні складені числа, позначивши всі кратні вибраних чисел.

Крок 3) Потім виберіть наступне просте або найменше непозначене число у списку та повторіть крок 2.

Крок 4) Повторюйте попередній крок, доки значення x не стане меншим або дорівнює квадратному кореню з n (x<=Алгоритм Решето Ератосфена).

Примітка: Математичні міркування досить прості. Діапазон чисел n можна розкласти на множники як-

n=a*b

Знову n =Алгоритм Решето Ератосфена*Алгоритм Решето Ератосфена

= (фактор менше, ніж Алгоритм Решето Ератосфена) * (фактор більше ніж Алгоритм «Решето Ератосфена».)

Отже, принаймні один із основні фактори або обидва мають бути <=Алгоритм Решето Ератосфена. Таким чином, переходячи до Алгоритм Решето Ератосфена буде достатньо.

Крок 5) Після цих чотирьох кроків решта непозначених чисел будуть усіма простими числами в заданому діапазоні n.

приклад:

Давайте візьмемо приклад і подивимося, як це працює.

Для цього прикладу ми знайдемо список простих чисел від 2 до 25. Отже, n=25.

Крок 1) На першому кроці ми візьмемо список чисел від 2 до 25, оскільки ми вибрали n=25.

Алгоритм Решето Ератосфена

Крок 2) Потім ми вибираємо найменше число зі списку, x. Спочатку x=2, оскільки це найменше просте число. Потім ми проходимо список і позначаємо кратні 2.

Число, кратне 2 для заданого значення n, таке: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Алгоритм «Решето Ератосфена».

Примітка: Синій колір позначає вибране число, а рожевий колір позначає вилучені кратні

Крок 3) Потім ми вибираємо наступне найменше непозначене число, яке дорівнює 3, і повторюємо останній крок, позначаючи кратні 3.

Алгоритм «Решето Ератосфена».

Крок 4) Ми повторюємо крок 3 таким же чином, поки x=Алгоритм «Решето Ератосфена». або 5.

Алгоритм «Решето Ератосфена».

Крок 5) Решта непозначених чисел будуть простими числами від 2 до 25.

Алгоритм «Решето Ератосфена».

СТАТТІ ПО ТЕМІ

Псевдокод

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

Решето Ератосфена C/C++ Приклад коду

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    } 
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
}

вихід:

2 3 5 7 11 13 17 19 23

Решето Ератосфена Python Приклад програми

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

вихід:

2
3
5
7
11
13
17
19
23

Сегментоване сито

Ми бачили, що решето Ератосфена потрібне для проходження циклу по всьому діапазону чисел. Таким чином, для зберігання чисел потрібно O(n) пам’яті. Ситуація ускладнюється, коли ми намагаємося знайти прості числа у величезному діапазоні. Неможливо виділити такий великий простір пам’яті для більшого n.

Алгоритм можна оптимізувати, додавши деякі нові функції. Ідея полягає в тому, щоб розділити діапазон чисел на менші сегменти та обчислити прості числа в цих сегментах один за іншим. Це ефективний спосіб зменшити складність простору. Цей метод називається a сегментоване сито.

Оптимізації можна досягти наступним чином:

  1. За допомогою простого сита знайдіть прості числа від 2 до Сегментоване сито і зберігати їх у масиві.
  2. Розділіть діапазон [0…n-1] на декілька сегментів розміром щонайбільше Сегментоване сито
  3. Для кожного сегмента повторіть сегмент і позначте кратне простим числам, знайденим на кроці 1. Для цього кроку потрібно O(Сегментоване сито) при макс.

Для звичайного сита потрібно O(n) допоміжного простору пам’яті, тоді як для сегментованого сита потрібно O(Сегментоване сито), що є великим покращенням для великого n. Цей метод має недолік ще й тому, що він не покращує часову складність.

Аналіз складності

Складність простору:

Алгоритм простого решета Ератосфена потребує O(n) пам’яті. І сегментоване решето вимагає
O(Аналіз складності) допоміжне приміщення.

Складність часу:

Часова складність звичайного решета алгоритму Ератосфена становить O(n*log(log(n))). Причини цієї складності обговорюються нижче.

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

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

Гармонійну прогресію суми простих чисел можна вирахувати як log(log(n)).

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

Отже, часова складність буде-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * log(log(n))

Таким чином, часова складність O(n * log(log(n)))

Далі ви дізнаєтеся про Трикутник Паскаля

Підсумки

  • Решето Ератосфена відфільтровує прості числа у заданій верхній межі.
  • Фільтрування простого числа починається з найменшого простого числа «2». Це робиться ітераційно.
  • Ітерація виконується до квадратного кореня з n, де n — заданий діапазон чисел.
  • Після цих ітерацій числа, які залишаються, є простими числами.

Вам може сподобатися: