Эратосфен способ нахождения простых чисел

Содержание

Решето Эратосфена
Время работы
Линейное решето
Алгоритм
Применения
Решето Эратосфена — алгоритм определения простых чисел
Решето Эратосфена
Время работы
Линейное решето
Алгоритм
Применения
Волшебное решето Эратосфена

Решето Эратосфена

Определение. Целое положительное число называется простым, если оно имеет ровно два различных натуральных делителя — единицу и самого себя. Единица простым числом не считается.

Решето Эратосфена (англ. sieve of Eratosthenes) — алгоритм нахождения всех простых чисел от $1$ до $n$ .

Основная идея соответствует названию алгоритма: запишем ряд чисел $1, 2,\ldots, n$ , а затем будем вычеркивать

сначала числа, делящиеся на $2$ , кроме самого числа $2$ ,

потом числа, делящиеся на $3$ , кроме самого числа $3$ ,

с числами, делящимися на $4$ , ничего делать не будем — мы их уже вычёркивали,

потом продолжим вычеркивать числа, делящиеся на $5$ , кроме самого числа $5$ ,

Самая простая реализация может выглядеть так:

Этот код сначала помечает все числа, кроме нуля и единицы, как простые, а затем начинает процесс отсеивания составных чисел. Для этого мы перебираем в цикле все числа от $2$ до $n$ , и, если текущее число простое, то помечаем все числа, кратные ему, как составные.

Если память позволяет, то для оптимизации скорости лучше использовать не вектор bool , а вектор char — но он займёт в 8 раз больше места. Компьютер не умеет напрямую оперировать с битами, и поэтому при индексации к vector он сначала достаёт нужный байт, а затем битовыми операциями получает нужное значение, что занимает приличное количество времени.

Время работы

Довольно легко показать, что асимптотическое время работы алгоритма хотя бы не хуже, чем $O(n \log n)$ : даже если бы мы входили в цикл вычёркиваний для каждого числа, не проверяя его сначала на простоту, суммарно итераций было бы

\[ \sum_k \frac = \frac <2>+ \frac <3>+ \frac <4>+ \ldots + \frac = O(n \log n) \]

Здесь мы воспользовались асимптотикой гармонического ряда.

У исходного алгоритма асимптотика должна быть ещё лучше. Чтобы найти её точнее, нам понадобятся два факта про простые числа:

Простых чисел от $1$ до $n$ примерно $\frac<\ln n>$ .

Простые числа распределены без больших «разрывов» и «скоплений», то есть $k$ -тое простое число примерно равно $k \ln k$ .

Мы можем упрощённо считать, что число $k$ является простым с «вероятностью» $\frac<1><\ln n>$ . Тогда, время работы алгоритма можно более точнее оценить как

\[ \sum_k \frac<1> <\ln k>\frac \approx n \int \frac<1> = n \ln \ln k \Big |_2^n = O(n \log \log n) \]

Асимптотику алгоритма можно улучшить и дальше, до $O(n)$ .

Линейное решето

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

Обозначим за $d(k)$ минимальный простой делитель числа $k$ и заметим следующий факт: у составного числа $k$ есть единственное представление $k = d(k) \cdot r$ , и при этом у числа $r$ нет простых делителей меньше $d(k)$ .

Идея оптимизации состоит в том, чтобы перебирать этот $r$ , и для каждого перебирать только нужные множители — а именно все от $2$ до $d(r)$ включительно.

Алгоритм

Немного обобщим задачу — теперь мы хотим посчитать для каждого числа $k$ на отрезке $[2, n]$ его минимальный простой делитель $d_k$ , а не только определить его простоту.

Изначально массив $d$ заполним нулями, что означает, что все числа предполагаются простыми. В ходе работы алгортима этот массив будет постепенно заполняться. Помимо этого, будем поддерживать список $p$ всех найденных на текущий момент простых чисел.

Теперь будем перебирать число $k$ от $2$ до $n$ . Если это число простое, то есть $d_k = 0$ , то присвоим $d_k = k$ и добавим $k$ в список $p$ .

Дальше, вне зависимости от простоты $k$ , начнём процесс расстановки значений в массиве $d$ — переберем найденные простые числа $p_i$ , не превосходящие $d_k$ , и сделаем присвоение $d_ = p_i$ .

Алгоритм требует как минимум в 32 раза больше памяти, чем обычное решето, потому что требуется хранить делитель ( int , 4 байта) вместо одного бита на каждое число. Линейное решето хоть и имеет лучшую асимптотику, но на практике проигрывает также и по скорости оптимизированному варианту решета Эратосфена.

Применения

Массив $d$ он позволяет искать факторизацию любого числа $k$ за время порядка размера этой факторизации:

\[ factor(k) = \ \cup factor(k / d(k)) \]

Знание факторизации всех чисел — очень полезная информация для некоторых задач. Ленейное решето интересно не своим временем работы, а именно этим массивом минимальных простых делителей.

Источник

Решето Эратосфена — алгоритм определения простых чисел

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

Чтобы понять данный алгоритм, вспомним, что числа являются простыми, если делятся только на единицу и самих себя. Первое простое число — это 2, второе простое число — это 3. Теперь начнем рассуждать:

Все четные числа, кроме двойки, — составные, т. е. не являются простыми, так как делятся не только на себя и единицу, а также еще на 2.
Все числа кратные трем, кроме самой тройки, — составные, так как делятся не только на самих себя и единицу, а также еще на 3.
Число 4 уже выбыло из игры, так как делится на 2.
Число 5 простое, так как его не делит ни один простой делитель, стоящий до него.
Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

Последний пункт вытекает из того, что сложные числа всегда можно представить как произведение простых. Поэтому если одно сложное число делится на другое сложное, то первое должно делиться на делители второго. Например, 12 делится на 6, делителями которого являются 2 и 3. Число 12 делится и на 2, и на 3.

Алгоритм Эратосфена как раз заключается в последовательной проверке делимости чисел на предстоящие простые числа. Сначала берется первое простое и из ряда натуральных чисел высеиваются все кратные ему. Затем берется следующее простое и отсеиваются все кратные ему и так далее.

При реализации алгоритма Эратосфена на языке программирования есть некоторая сложность. Допустим, мы помещаем натуральные числа до заданного числа n в массив. Далее в процессе выполнения алгоритма будем заменять обнаруженные сложные числа нулями. После выполнения алгоритма те ячейки массива, которые не содержат нули, содержат простые числа, которые выводятся на экран.

Однако индексация массива начинается с нуля, а простые числа начинаются с двойки. Эта проблема решаема, но добавляет сложности в код. Поскольку алгоритм Эратосфена не такой уж простой, легче пренебречь началом и взять массив от 0 до n . Здесь важнее индексы, чем значения элементов. Значениями может быть True, обозначающее простое число, и False, обозначающее сложное число.

В данном примере реализации алгоритма Эратосфена список заполняется числами от 0 до n включительно так, что индексы элементов совпадают с их значениями. Далее все непростые числа заменяются нулями:

Источник

Решето Эратосфена

Решето Эратосфена (англ. sieve of Eratosthenes) — алгоритм нахождения всех простых чисел от $1$ до $n$.

Основная идея соответствует названию алгоритма: запишем ряд чисел $1, 2,\ldots, n$, а затем будем вычеркивать

сначала числа, делящиеся на $2$, кроме самого числа $2$,
потом числа, делящиеся на $3$, кроме самого числа $3$,
с числами, делящимися на $4$, ничего делать не будем — мы их уже вычёркивали,
потом продолжим вычеркивать числа, делящиеся на $5$, кроме самого числа $5$,

Самая простая реализация может выглядеть так:

Этот код сначала помечает все числа, кроме нуля и единицы, как простые, а затем начинает процесс отсеивания составных чисел. Для этого мы перебираем в цикле все числа от $2$ до $n$, и, если текущее число простое, то помечаем все числа, кратные ему, как составные.

Время работы

Довольно легко показать, что асимптотическое время работы алгоритма хотя бы не хуже, чем $O(n \log n)$: даже если бы мы входили в цикл вычёркиваний для каждого числа, не проверяя его сначала на простоту, суммарно итераций было бы

$$ \sum_k \frac = \frac <2>+ \frac <3>+ \frac <4>+ \ldots + \frac = O(n \log n) $$

Здесь мы воспользовались асимптотикой гармонического ряда.

Простых чисел от $1$ до $n$ примерно $\frac<\ln n>$ .

Простые числа распределены без больших «разрывов» и «скоплений», то есть $k$-тое простое число примерно равно $k \ln k$.

Мы можем упрощённо считать, что число $k$ является простым с «вероятностью» $\frac<1><\ln n>$. Тогда, время работы алгоритма можно более точнее оценить как

$$ \sum_k \frac<1> <\ln k>\frac \approx n \int \frac<1> = n \ln \ln k \Big |_2^n = O(n \log \log n) $$

Асимптотику алгоритма можно улучшить и дальше, до $O(n)$.

Линейное решето

Обозначим за $d(k)$ минимальный простой делитель числа $k$ и заметим следующий факт: у составного числа $k$ есть единственное представление $k = d(k) \cdot r$, и при этом у числа $r$ нет простых делителей меньше $d(k)$.

Идея оптимизации состоит в том, чтобы перебирать этот $r$, и для каждого перебирать только нужные множители — а именно все от $2$ до $d(r)$ включительно.

Алгоритм

Немного обобщим задачу — теперь мы хотим посчитать для каждого числа $k$ на отрезке $[2, n]$ его минимальный простой делитель $d_k$, а не только определить его простоту.

Изначально массив $d$ заполним нулями, что означает, что все числа предполагаются простыми. В ходе работы алгоритма этот массив будет постепенно заполняться. Помимо этого, будем поддерживать список $p$ всех найденных на текущий момент простых чисел.

Теперь будем перебирать число $k$ от $2$ до $n$. Если это число простое, то есть $d_k = 0$, то присвоим $d_k = k$ и добавим $k$ в список $p$.

Дальше, вне зависимости от простоты $k$, начнём процесс расстановки значений в массиве $d$ — переберем найденные простые числа $p_i$, не превосходящие $d_k$, и сделаем присвоение $d_ = p_i$.

Применения

Массив $d$ позволяет искать факторизацию любого числа $k$ за время порядка размера этой факторизации:

$$ factor(k) = \ \cup factor(k / d(k)) $$ Знание факторизации всех чисел — очень полезная информация для некоторых задач. Линейное решето интересно не своим временем работы, а именно этим массивом минимальных простых делителей.

Источник

Волшебное решето Эратосфена

Наверняка все, кто читает этот пост не раз использовали, или хотя бы слышали о решете Эратосфена — методе отыскания простых чисел. Сама проблема получения простых чисел занимает ключевое место в математике, на ней основаны некоторые криптографические алгоритмы, например RSA. Есть довольно много подходов к данной задаче, но в этой статье я остановлюсь на некоторых модификациях самого простого из них — решета Эратосфена.
Принцип решета прост: пускай нам нужно отыскать простые числа в промежутке от единицы до некоторого N

Arrays.fill(isPrime, true );

isPrime[ 1 ] = false ;

for ( int i= 2 ; i*i if (isPrime[i])

for ( int j=i*i; j false ;

int h = m % primes[i];
int j = h == 0 ? 0 : primes[i] — h;

for (; j false ;

Так можно справляться с диапазонами, достаточно удаленными от нуля. Теперь подходим к самому интересному моменту: а что, если нам необходимо вывести простые числа от 0 до N = 10^8? Если вспомнить асимптотику, то это на первый взгляд кажется реальным даже для обычного решета, но посмотрев на затраты памяти: 10^8 * 4 = 400МБ мы видим что задача не такая тривиальная, особенно, если у нас есть жесткие временные ограничения. Для решения этой задачи можно выделить два подхода, а именно:

упаковка решета

учитывание кэш-памяти

Рассмотрим их немного подробнее. Упаковка заключается вот в чем: в современных языках программирования тип boolean занимает в среднем от одного до четырех байт, хотя его можно закодировать всего одним битом. Поэтому мы можем создавать массив целых чисел и работать с каждым из них как с побитовой маской, тем самым экономя память в 8-30 раз. Преимущества видны сразу, но теперь остановимся чуть подробнее на второй идее, которая гарантированно ускоряет решето в несколько раз
Многим известно, что в нашем компьютере между процессорной и оперативной памятью находится кэш-память, работа с ней проводится намного быстрее, чем с оперативной, но ее размеры ограничены. Например, при работе с большим массивом, процессор загружает в кэш некоторую его часть, работает с ней, потом переносит обратно в оперативную, загружает другую и так далее. А теперь вспомним наш алгоритм решета: каждое простое число мы вычеркивали из всего массива, проходясь по нему от начала до конца. Поэтому процессор много раз будет загружать в кэш разные отрезки массива и скорость на этом будет сильно теряться. Данный подход предлагает минимизировать затраты на копирование массива из одной памяти в другую. Это сделать несложно если весь наш промежуток разделить на кусочки, до 3*10^4 элементов, что приблизительно равно размеру кэша и работать с ними по-порядку. Тогда мы за минимальное количество загрузок разберемся со всем массивом. Примерно так это будет выглядеть:

int CACHE = 30000 ; // размер кэша

int M = ( int ) Math .sqrt(N)+ 1 ;

int primes = new int [P]; // массив простых чисел до корня из N

boolean segment = new boolean [CACHE]; // вторичное решето

for ( int I=M- 1 ; I true );

for ( int i= 0 ; i int h = I % primes[i];

int j = h > 0 ? primes[i] — h : 0 ;

for (; j false ;

>

for ( int i= 0 ; i if (segment[i] && (i + I out .println(i+I); // выводим простое число на экран

>

>

>

Используя этот метод мы очень сильно ускоряем наше решето, практически не усложняя его, для многих задач это ощутимо помогает, например, одна из них: TDPRIMES, на этой задаче можно потренироваться и хорошо увидеть что обычное решето не укладывается в 10с, а сегментированное проходит за 2.8.

Источник