Сито Эратостена в 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.

Число n, кратное 2, равно: 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 нецелесообразно.

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

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

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

Обычное сито требует O(n) вспомогательной памяти, тогда как сегментированное сито требует O(), что является существенным улучшением для больших n. У этого метода есть и недостаток, поскольку он не улучшает временную сложность.

Анализ сложности

Понимание пространственной и временной сложности помогает выбрать между обычным и сегментированным ситом для задачи заданного размера.

Космическая сложность:

Простой алгоритм решета Эратосфена требует O(n) памяти. Сегментированное решето требует O(n)) вспомогательное пространство.

Сложность времени:

Временная сложность обычного алгоритма решета Эратосфена составляет 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 * журнал(журнал(n))

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

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

Часто задаваемые вопросы (FAQ)