Решето алгоритма Эратосфена: Python, C++ Пример

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

Слово "решетоозначает посуду, которая фильтрует вещества. Таким образом, ситовой алгоритм в 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 =*

= (коэффициент меньше, чем ) * (коэффициент больше, чем )

Итак, по крайней мере, один из главные факторы или оба должны быть <=. Таким образом, переходя к будет достаточно.

Шаг 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.

Алгоритм может быть оптимизирован путем введения некоторых новых функций. Идея состоит в том, чтобы разделить диапазон чисел на более мелкие сегменты и вычислить простые числа в этих сегментах одно за другим. Это эффективный способ уменьшить сложность пространства. Этот метод называется сегментированное сито.

Оптимизация может быть достигнута следующим образом:

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

Итак, временная сложность будет:

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

= n * журнал(журнал(n))

Таким образом, временная сложность O(n * log(log(n)))

Далее вы узнаете о Треугольник Паскаля

Резюме

• Решето Эратосфена отфильтровывает простые числа в заданном верхнем пределе.
• Фильтрация простых чисел начинается с наименьшего простого числа «2». Это делается итеративно.
• Итерация выполняется до квадратного корня из n, где n — заданный диапазон чисел.
• После этих итераций оставшиеся числа являются простыми числами.