Как найти простое число по его номеру

Как узнать простое число по его номеру

8 декабря 2017

Время чтения: 7 минут

Простое число — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя.

Чтобы проверить является ли какое-то число простым, напрашивается наивный метод решения – проверить делимость его на все натуральные числа от 1 до n (хотя достаточно лишь до квадратного корня из него). Если в какой-то момент остаток от деления даст 0 (то есть число поделилось без остатка), значит оно составное, а в противном случае является простым.

Такой алгоритм прост, но требует довольно много проверок на делимость, из-за чего может быть применён для проверки небольшого числа. А что будет, если применить его для поиска простого числа по заданному номеру n?

Решение кажется очевидным: начнём перебирать подряд числа и проверять их на простоту. Как только обнаружим n простых чисел, остановимся и вернём в результате последнее найденное число. Однако, даже для не очень большого числа n данный метод будет работать чрезвычайно долго, поскольку чем больше будет число, тем дольше будут перебираться его делители.

Вот тут нам на помощь и приходит быстрый алгоритм — решето Эратосфена. Данный алгоритм позволяет найти все простые числа в интервале от 2 до N за довольно короткое время, но нам то нужно найти n-ое простое число, а про индексы в данном алгоритме ничего не сказано. Если бы можно было узнать, в каком интервале находится n-ое простое число, то задача была бы мгновенно решена применением решета. Однако как же решить данную задачу, не зная примерное значение числа?

Как работает решето Эратосфена

Как работает решето Эратосфена

Мы предлагаем следующее решение: получим число n и создадим два массива размерности n: primes – массив для хранения будущих простых чисел и numbers – массив для хранения обычных чисел для применения просеивания решетом. Заполним массив numbers числами от 0 до n – 1, а в нулевой элемент массива primes положим 2, поскольку 2 — первое простое число.

Код программы для поиска простого числа по его номеру

#include <iostream>

int main () { 
    int n; 
    
    std::cout << "Enter number of prime number: ";
    std::cin >> n; // считываем номер простого числа, которое нужно найти

    int size = n; // число элементов для массива чисел для просеивания
    int *primes = new int[n]; // массив простых чисел
    int *numbers = new int[size]; // массив для чисел

    for (int i = 0; i < size; i++)
        numbers[i] = i; // заполняем массив (число равно индексу элемента)

    primes[0] = 2; // первое простое число - 2
    int i = 0; // индекс текущего простого числа

    while (i < n) {
        int p = primes[i++]; // запоминаем текущее простое число

        for (int j = p * 2; j < size; j += p)
            numbers[j] = 0; // обнуляем все кратные ему числа в массиве

        while (numbers[p + 1] == 0)
            p++; // ищем следующее ненулевое число

        if (p + 1 >= size) { // если выйдем за границы, расширяем массив
            int *tmp = new int[size * 2];

            for (int k = 0; k < size; k++)
                tmp[k] = numbers[k];

            delete[] numbers;

            size *= 2;
            numbers = tmp;

            for (int j = size / 2; j < size; j++)
                numbers[j] = j; // заполняем новую часть массива числами

            i = 0; // возвращаемся к начальной стадии просеивания
        } else 
            primes[i] = p + 1; // запоминаем новое простое число
    }

    std::cout << n << " prime number is " << primes[n - 1] << std::endl;

    delete[] numbers;
    delete[] primes; 
}

Теперь нам нужно искать числа до тех пор, пока не найдём все n, поэтому обнуляем переменную i, обозначающую текущий индекс простого числа и запускаем цикл пока с условием i < n.

Запоминаем в переменной p текущее простое число (на первой итерации это будет 2), увеличивая текущий индекс простого числа на 1 и просеивая массив чисел от 2p до размера массива чисел (тем элементам массива, где стоят кратные p числа (кроме самого p), проставляем нули, после чего ищем первое ненулевое число — оно и будет следующим простым числом.

В дальнейшем может возникнуть проблема, что n-ое простое число ещё не найдено, а массив чисел уже закончился. Простым решением данной проблемы будет увеличение его размера в два раза и до заполнение числами. Но если так сделать, то в нём останутся числа, кратные тем, что ещё уже были просеяны, и требуется их обработать. Простым решением данной проблемы является запуск алгоритма сначала, а именно обнуление индекса текущего простого числа, благодаря чему все операции просеивания будут проведены повторно, но уже для нового более длинного массива.

Если же изменение массива не требовалось, в массив primes просто записывается найденное простое число (первое ненулевое число в массиве numbers).

Когда же цикл завершён, достаточно просто вывести n – 1 элемент в массиве primes или весь массив, если нужны все простые числа до указанного номера.

Фото Перминова Андрея, автора этой статьи

Программист, сооснователь programforyou.ru, в постоянном поиске новых задач и алгоритмов

Языки программирования: Python, C, C++, Pascal, C#, Javascript

Выпускник МГУ им. М.В. Ломоносова

Алгоритмы поиска простых чисел

Время на прочтение
6 мин

Количество просмотров 134K

«Самое большое простое число 232582657-1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс

Натуральное число называется простым, если оно имеет только два различных делителя: единицу и само себя. Задача поиска простых чисел не дает покоя математикам уже очень давно. Долгое время прямого практического применения эта проблема не имела, но все изменилось с появлением криптографии с открытым ключом. В этой заметке рассматривается несколько способов поиска простых чисел, как представляющих исключительно академический интерес, так и применяемых сегодня в криптографии.

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

Решето Эратосфена — алгоритм, предложенный древнегреческим математиком Эратосфеном. Этот метод позволяет найти все простые числа меньше заданного числа n. Суть метода заключается в следующем. Возьмем набор чисел от 2 до n. Вычеркнем из набора (отсеим) все числа делящиеся на 2, кроме 2. Перейдем к следующему «не отсеянному» числу — 3, снова вычеркиваем все что делится на 3. Переходим к следующему оставшемуся числу — 5 и так далее до тех пор пока мы не дойдем до n. После выполнения вышеописанных действий, в изначальном списке останутся только простые числа.

Алгоритм можно несколько оптимизировать. Так как один из делителей составного числа n обязательно

$leqslant sqrt{n}$, алгоритм можно останавливать, после вычеркивания чисел делящихся на

$sqrt{n}$.

Иллюстрация работы алгоритма из Википедии:

image

Сложность алгоритма составляет

$O(n loglog n)$, при этом, для хранения информации о том, какие числа были вычеркнуты требуется

$O(n)$ памяти.

Существует ряд оптимизаций, позволяющих снизить эти показатели. Прием под названием wheel factorization состоит в том, чтобы включать в изначальный список только числа взаимно простые с несколькими первыми простыми числами (например меньше 30). В теории предлагается брать первые простые примерно до

$sqrt{log n}$. Это позволяет снизить сложность алгоритма в

$loglog n$ раз. Помимо этого для уменьшения потребляемой памяти используется так называемое сегментирование. Изначальный набор чисел делится на сегменты размером

$leqslant sqrt{n}$ и для каждого сегмента решето Эратосфена применяется по отдельности. Потребление памяти снижается до

$O(sqrt{n})$.

Решето Аткина

Более совершенный алгоритм отсеивания составных чисел был предложен Аткином и Берштайном и получил название Решето Аткина. Этот способ основан на следующих трех свойствах простых чисел.

Свойство 1

Если n — положительное число, не кратное квадрату простого числа и такое, что

$n equiv 1(mod 4)$. То n — простое, тогда и только тогда, когда число корней уравнения

$4x^2+y^2=n$ нечетно.

Свойство 2

Если n — положительное число, не кратное квадрату простого числа и такое, что

$n equiv 1(mod 6)$. То n — простое, тогда и только тогда, когда число корней уравнения

$3x^2+y^2=n$ нечетно.

Свойство 3

Если n — положительное число, не кратное квадрату простого числа и такое, что

$n equiv 11(mod 12)$. То n — простое, тогда и только тогда, когда число корней уравнения

$3x^2-y^2=n$ нечетно.

Доказательства этих свойств приводятся в этой статье.

На начальном этапе алгоритма решето Аткина представляет собой массив A размером n, заполненный нулями. Для определения простых чисел перебираются все

$x, y < sqrt n$. Для каждой такой пары вычисляется

$4x^2+y^2$,

$3x^2+y^2$,

$3x^2-y^2$ и значение элементов массива

$A[4x^2+y^2]$,

$A[3x^2+y^2]$,

$A[3x^2-y^2]$ увеличивается на единицу. В конце работы алгоритма индексы всех элементов массива, которые имеют нечетные значения либо простые числа, либо квадраты простого числа. На последнем шаге алгоритма производится вычеркивание квадратов оставшихся в наборе чисел.

Из описания алгоритма следует, что вычислительная сложность решета Аткина и потребление памяти составляют

$O(n)$. При использовании wheel factorization и сегментирования оценка сложности алгоритма снижается до

$O(n / loglog n)$, а потребление памяти до

$O(sqrt{n})$.

Числа Мерсенна и тест Люка-Лемера

Конечно при таких показателях сложности, даже оптимизированное решето Аткина невозможно использовать для поиска по-настоящему больших простых чисел. К счастью, существуют быстрые тесты, позволяющие проверить является ли заданное число простым. В отличие от алгоритмов решета, такие тесты не предназначены для поиска всех простых чисел, они лишь способны сказать с некоторой вероятностью, является ли определенное число простым.

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

$2^p-1$, где p — натуральное число. Такие числа называются числами Мерсенна.

Тест Люка-Лемера утверждает, что число Мерсенна

$M_p=2^p-1$ простое тогда и только тогда, когда p — простое и

$M_p$ делит нацело

$(p-1)$-й член последовательности

$S_k$ задаваемой рекуррентно:

$S_1=4, S_k=S_{k-1}^2-2$ для

$k > 1$.

Для числа

$M_p$ длиной p бит вычислительная сложность алгоритма составляет

${displaystyle O(p^{3})}$.

Благодаря простоте и детерминированности теста, самые большие известные простые числа — числа Мерсенна. Самое большое известное простое число на сегодня —

$2^{82,589,933}-1$, его десятичная запись состоит из 24,862,048 цифр. Полюбоваться на эту красоту можно здесь.

Теорема Ферма и тест Миллера-Рабина

Простых чисел Мерсенна известно не очень много, поэтому для криптографии с открытым ключом необходим другой способ поиска простых чисел. Одним из таким способов является тест простоты Ферма. Он основан на малой теореме Ферма, которая гласит, что если n — простое число, то для любого a, которое не делится на n, выполняется равенство

$a^{n-1}equiv 1{pmod {n}}$. Доказательство теоремы можно найти на Википедии.

Тест простоты Ферма — вероятностный тест, который заключается в переборе нескольких значений a, если хотя бы для одного из них выполняется неравенство

$a^{n-1} notequiv 1 pmod n$, то число n — составное. В противном случае, n — вероятно простое. Чем больше значений a использовано в тесте, тем выше вероятность того, что n — простое.

К сожалению, существуют такие составные числа n, для которых сравнение

$a^{n-1}equiv 1{pmod {n}}$ выполняется для всех a взаимно простых с n. Такие числа называются числам Кармайкла. Составные числа, которые успешно проходят тест Ферма, называются псевдопростыми Ферма. Количество псевдопростых Ферма бесконечно, поэтому тест Ферма — не самый надежный способ определения простых чисел.

Тест Миллера-Рабина

Более надежных результатов можно добиться комбинируя малую теорему Ферма и тот факт, что для простого числа p не существует других корней уравнения

$x^2 equiv 1 pmod p$, кроме 1 и -1. Тест Миллера-Рабина перебирает несколько значений a и проверяет выполнение следующих условий.

Пусть p — простое число и

$p-1=2^sd$, тогда для любого a справедливо хотя бы одно из условий:

  1. $a^{d}equiv pm1{pmod {p}}$
  2. Существует целое число r < s такое, что $a^{2^{r}d}equiv -1{pmod {p}}$

По теореме Ферма

$a^{p-1}equiv1pmod p$, а так как

$p-1=2^sd$ из свойства о корнях уравнения

$x^2 equiv 1 pmod p$ следует что если мы найдем такое a, для которого одно из условий не выполняется, значит p — составное число. Если одно из условий выполняется, число a называют свидетелем простоты числа n по Миллеру, а само число n — вероятно простым.

Чем больше свидетелей простоты найдено, тем выше вероятность того, что n — простое. Согласно теореме Рабина вероятность того, что случайно выбранное число a окажется свидетелем простоты составного числа составляет приблизительно

$1/4$.

Следовательно, если проверить k случайных чисел a, то вероятность принять составное число за простое

$approx(1/4)^k$.

Сложность работы алгоритма

$O(klog^3p)$, где k — количество проверок.

Благодаря быстроте и высокой точности тест Миллера-Рабина широко используется при поиске простых чисел. Многие современные криптографические библиотеки при проверке больших чисел на простоту используют только этот тест и, как показал Мартин Альбрехт в своей работе , этого не всегда оказывается достаточно.

Он смог сгенерировать такие составные числа, которые успершно прошли тест на простоту в библиотеках OpenSSL, CryptLib, JavaScript Big Number и многих других.

Тест Люка и Тест Baillie–PSW

Чтобы избежать уязвимости, связанные с ситуациями, когда сгенерированное злоумышленником составное число, выдается за простое, Мартин Альбрехт предлагает использовать тест Baillie–PSW. Несмотря на то, что тест Baillie–PSW является вероятностным, на сегодняшний день не найдено ни одно составное число, которое успешно проходит этот тест. За нахождение подобного числа в 1980 году авторы алгоритма пообещали вознаграждение в размере $30. Приз пока так и не был востребован.

Ряд исследователей проверили все числа до

$2^{64}$ и не обнаружили ни одного составного числа, прошедшего тест Baillie–PSW. Поэтому, для чисел меньше

$2^{64}$ тест считается детерминированным.

Суть теста сводится к последовательной проверке числа на простоу двумя различными методами. Один из этих методов уже описанный выше тест Миллера-Рабина. Второй — тест Люка на сильную псевдопростоту.

Тест Люка на сильную псевдопростоту

Последовательности Люка — пары рекуррентных последовательностей

${U_{n}(P,Q)}, {V_{n}(P,Q)}$, описываемые выражениями:

${displaystyle U_{0}(P,Q)=0,quad U_{1}(P,Q)=1,quad U_{n+2}(P,Q)=Pcdot U_{n+1}(P,Q)-Qcdot U_{n}(P,Q),,ngeq 0}$

${displaystyle V_{0}(P,Q)=2,quad V_{1}(P,Q)=P,quad V_{n+2}(P,Q)=Pcdot V_{n+1}(P,Q)-Qcdot V_{n}(P,Q),,ngeq 0}$

Пусть

$U_n(P,Q)$ и

$V_n(P,Q)$ — последовательности Люка, где целые числа P и Q удовлетворяют условию

${displaystyle D=P^{2}-4Qneq 0}$

Вычислим символ Якоби:

$left({frac {D}{p}}right)=varepsilon$.

Найдем такие r, s для которых выполняется равенство

$n-ε=2^rs$

Для простого числа n выполняется одно из следующих условий:

  1. n делит $U_s$
  2. n делит $V_{2^js}$ для некоторого j < r

В противном случае n — составное.

Вероятность того, что составное число n успешно пройдет тест Люка для заданной пары параметров P, Q не превышает 4/15. Следовательно, после применения теста k раз, эта вероятность составляет

$(4/15)^k$.

Тесты Миллера-Рабина и Люка производят не пересекающиеся множества псевдопростых чисел, соответственно если число p прошло оба теста, оно простое. Именно на этом свойстве основывается тест Baillie–PSW.

Заключение

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

$10^8$. Затем для каждого числа p из списка, с помощью теста Люка-Лемера, на простоту проверяется

$M_p=2^p-1$.

Чтобы сгенерировать большое простое число в криптографических целях, выбирается случайное число a и проверяется тестом Миллера-Рабина или более надежным Baillie–PSW. Согласно теореме о распределении простых чисел, у случайно выбранного числа от 1 до n шанс оказаться простым примерно равен

${frac {1}{ln n}}$. Следовательно, чтобы найти простое число размером 1024 бита, достаточно перебрать около тысячи вариантов.

P.S. Исходники

Реализацию всех описанных алгоритмов на Go можно посмотреть на GitHub.

  • 1-е простое число: p(1)=2
  • 2-е простое число: p(2)=3
  • 3-е простое число: p(3)=5
  • 4-е простое число: p(4)=7
  • 5-е простое число: p(5)=11
  • n-е простое число: p(n)=? — Какая общая формула n-го члена последовательности простых чисел?

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

Есть несколько формул, которые дают какой-то ограниченный набор простых чисел. Есть формулы, которые дают неограниченный набор простых чисел, но среди значений, которые вычисляются по этим формулам, попадаются и составные числа, то есть требуется дополнительная проверка получаемых результатов.

Подробный разбор различных формул, связанных с порождением простых чисел, можно найти в журнале “Квант”, №5 за 1975 год. По счастью, он доступен по Сети. В частности, там упоминаются полиномиальные многочлены и формула Джулии Робинсон, которая на данный момент удовлетворяет задачи порождения простых чисел наилучшим образом.

автор вопроса выбрал этот ответ лучшим

ОлегТ
[31.7K]

7 месяцев назад 

Вроде длинный ответ надо давать. А как его тут дашь, если ответ простой и тут не разгуляешься.


Давайте поймем, что же это за простые числа. Это Натуральные числа больше 1, такие что имеют только 2 делителя: единицу и само число. А числа, которые имеют более 2 делителей – будут составными. Составные числа можно разложить на простые множители.

Теперь попробуем решить несколько иную задачу: Пусть есть некое число N. Как понять простое оно или составное?

Надо просто проверить делится ли оно на что то еще кроме “1 и N”. Понятно, что если делиться, то делитель будет больше 1 и меньше N.

Немножко поразмыслив, можно понять, что делимость можно проверять только на простые числа из этого диапазона. А еще подумав, можно понять, что можно проверять не все числа, а до некого p(n), такого что p(n)² ≤ N, а p(n+1)² > N. И даже если после проверки окажется, что все p(n) – не являются делителями N, то есть N – будет простым. Все равно неизвестен его номер. Оно может идти по счету “k”-тым после “n”. N = p(n+k). И сколько этих “k” может быть неизвестно.


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

А числа находят путем проверки делимости. Занимаются этим конечно компьютеры.

simpl
[130K]

7 месяцев назад 

Нет никакой формулы нахождения простых чисел, есть большие доводы, что их распределение имеет случайный характер..

И не нужно придумывать ерунду и отсебятину..

Но есть алгоритмы нахождения ряда простых чисел, самый известный и древний – это т.н. “Решето Эратосфена”..

Для нахождения всех простых чисел вплоть до заданного, согласно Решету Эратосфена нужно:

  1. Выписать целые числа от двух до заданного числа, ограничивающего ряд

2.Вычеркнуть из списка числа кратные 2 до заданного числа

3.Первое не зачёркнутое число, большее чем 2, является простым

4.Вычеркнуть из ряда все числа, кратные найденному числу – это 3

Нужно начинать вычёркивание с заранее известного числа, например 2, потом все числа, кратные 2 и так до конца ряда, найти первое попавшееся не зачёркнутое число и вычеркнуть все последующие кратные ему..

Вычёркиваем все кратные числа первому не зачеркнутому..

В итоге – все не вычеркнутые числа в списке — простые числа.

Alex-soldi­er
[138]

более месяца назад 

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

Но по факту это синтетически скомпонованные и крайне замороченные выражения, которые сколько-нибудь пригодны для практического использования только для небольших интервалов n (обычно из-за того, что с ростом n происходит колоссальный рост вычислительной сложности выражения, и, в определенный момент, становится проще найти очередное по счету Простое число банальным Решетом).

Кстати о Решетах. Наиболее популярны три: Решето Эратосфена, Решето Аткина, Решето Сундарама. Аткин и Сундарам работают быстрее Эратосфена, но в них необходимо хранить большие массивы данных, поэтому их применение оправдано лишь на небольших начальных интервалах [2;N]. А вот Эратосфен при реализации оказывается более экономичным, поэтому обычно именно его используют для глубокого просеивания в программах поиска больших Простых чисел.

См. https://en.wikipedia­.org/wiki/Formula_fo­r_primes

См. https://mathworld.wo­lfram.com/PrimeFormu­las.html

См. https://ru.wikipedia­.org/wiki/Решето_Атк­ина

См. https://ru.wikipedia­.org/wiki/Решето_Сун­дарама

Знаете ответ?

1 / 1 / 0

Регистрация: 29.11.2014

Сообщений: 50

1

Решето Эратосфена. По номеру простого числа найти это число

13.12.2014, 00:28. Показов 8017. Ответов 2


Студворк — интернет-сервис помощи студентам

Найти n-ое по счёту простое число.
Пример:
1 2 3 4 5 6 7 8 9 10 11 Из них простые
1 2 3 5 7 11 порядковые номера 123456
Соответсвенно 5-ое простое число 7, второе 2.
//
У меня получается наоборот.
я пишут число, он мне выдаёт его номер.
а надо по номеру числа , найти само число.



0



Programming

Эксперт

94731 / 64177 / 26122

Регистрация: 12.04.2006

Сообщений: 116,782

13.12.2014, 00:28

2

3 / 3 / 2

Регистрация: 01.06.2013

Сообщений: 69

13.12.2014, 00:35

2

1. Находишь все простые числа в диапазоне и записываешь в новый массив
2. В массиве каждое число уже имеет свой номер.
3. Реализуешь вывод Определенного числа по номеру из массива.

а вообще покажи свой код



0



D_in_practice

342 / 342 / 331

Регистрация: 02.10.2014

Сообщений: 666

13.12.2014, 04:13

3

Лучший ответ Сообщение было отмечено dimashorokhov как решение

Решение

1 – не простое число

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
 
using namespace std;
 
int main(){
    
    const int SIZE = 100*1000;
    const int N = 9500;
    
    int n;
    do{
        cout << "n = ";
        cin >> n;
    }while(n < 0 || N < n);
    
    int a[SIZE];
    for (int i = 2; i < SIZE; ++i)
        a[i] = 1;
    
    int k = 1;
    int p = 2;
    while(k < n){
        for (int i = 2*p; i < SIZE; i += p)
            a[i] = 0;
        for (int i = p + 1; i < SIZE; ++i)
            if (a[i] == 1){
                p = i;
                break;
            }
            ++k;
    }
    
    cout << p << endl;  
}



1



Здравствуйте, дорогие читатели! Можете ли Вы сразу определить, является ли число 101 – простым? Или быстро перечислить все простые числа, меньше 102? Если да, то Вы почти наверняка пользуетесь алгоритмом, который сформулировал греческий математик Эратосфен еще до нашей эры. Если вдруг, Вы используете другой способ, то поделитесь им в комментариях.

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

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

Занимательно, что поисковик так и норовит подсунуть портрет Евклида, вместо портрета Эратосфена. Хотя, про Евклида и его алгоритм, я уже написала две статьи. Ну, раз великий интернет настаивает, то в конце этой публикации прикреплю ссылку на статью про алгоритм Евклида. Там можно полюбоваться его портретом

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

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

Название, на самом деле, говорящее. Эратосфен, действительно, отбирал простые числа при помощи своеобразного решета.

Конечно, постоянные читатели моего канала знают, что такое простые числа. Но, возможно эта статья попадется на глаза кому-то менее информированному, поэтому напомню:

Натуральное число, большее единицы, называют простым, если оно имеет всего два натуральных делителя: единицу и само это число

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

Легкий способ поиска простых чисел. Решето Эратосфена

При таком подходе, те числа, которые останутся не вычеркнутыми и будут являться простыми.

На самом деле, им можно пользоваться и для выделения простых чисел из какого-то отрезка натурального ряда, начинающегося не с единицы.

Ну что ж, посмотрим это на примере и вместе ответим на вопросы, которые я задала Вам в начале статьи.

Пример

Задание на картинке:

Легкий способ поиска простых чисел. Решето Эратосфена

Выполняем первый шаг алгоритма: записываем все числа от 2 до 102 в порядке возрастания. Можно записывать и вместе с единицей, но нужно помнить, что она не является простым числом.

Легкий способ поиска простых чисел. Решето Эратосфена

Вычеркиваем все четные числа, кроме двойки, так как они кратны двум:

Легкий способ поиска простых чисел. Решето Эратосфена

Вычеркиваем числа, кратные трем, кроме тройки:

Легкий способ поиска простых чисел. Решето Эратосфена

Давайте выясним, до каких пор этот процесс будет продолжаться:

Легкий способ поиска простых чисел. Решето Эратосфена

Получается, что вычеркивание будет продолжаться до тех пор, пока мы не вычеркнем числа кратные 10. Далее, я подробно не буду описывать каждый шаг. Суть уже ясна. И, не забываем зачеркнуть единицу.

При чем, задача упрощается, так как, например, числа кратные четырем, шести, восьми и десяти уже вычеркнуты. Ведь они также кратны и двум. По сути, остается вычеркнуть только те числа, которые кратны простым числам, находящимся в промежутке от 4 до 10.

Легкий способ поиска простых чисел. Решето Эратосфена

Таким образом, те числа, которые остались не вычеркнутыми и будут являться простыми. Давайте выпишем их:

Вот мы и получили ответ.

Если Вам понравилась статья, то обязательно ставьте лайки и комментируйте ее. Это поспособствует тому, чтобы ее увидело много людей!

Ссылка на статью про алгоритм Евклида, в которой можно полюбоваться его портретом:

Как Евклид находил наибольший общий делитель. Простейший способ

Добавить комментарий