Решето на Ератостен в Python & C++

Какво е ситото на Ератостен?

Решетото на Ератостен е най-простото сито за прости числа. Това е алгоритъм за прости числа, използван за откриване на всяко просто число в даден лимит. Съществуват няколко сита за прости числа, включително ситото на Ератостен, ситото на Аткин и ситото на Сундарам.

Думата "сито„“ се отнася до прибор, който филтрира вещества. В същия дух, алгоритъмът за сито в Python и други езици се отнася до метод, който филтрира прости числа от списък с цели числа.

Този алгоритъм филтрира прости числа, използвайки итеративен подход. Процесът на филтриране започва с най-малкото просто число. Простото число е естествено число, по-голямо от 1, което има само два делителя, а именно 1 и самото число. Numbers които не са прости числа, се наричат ​​съставни числа.

Защо да използваме ситото на Ератостен?

При метода „Рето на Ератостен“ първо се избира малко просто число и всички негови кратни се филтрират. Процесът протича в цикъл в даден диапазон, като ефективно се получава всяко просто число до n, без да се извършва пробно деление на всеки кандидат.

Това прави ситото по-бързо от проверката на простотата едно число наведнъж. То се използва широко в теорията на числата, криптографията, хеширането и конкурентното програмиране, където много прости числа трябва да бъдат генерирани бързо.

Например:

Нека вземем числовия диапазон от 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.

псевдо-Code

Следният псевдокод улавя основната структура на ситото на Ератостен, преди да го преведем в действителен код.

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++ Code Пример

По-долу е дадено пълно 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 Примерна програма

По-долу Python Програмата реализира същия алгоритъм, използвайки булев списък и while цикъл.

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))).

След това ще научите за Триъгълник на Паскал.

Въпроси и Отговори