If you're seeing this message, it means we're having trouble loading external resources on our website.

Если вы используете веб-фильтр, пожалуйста, убедитесь, что домены *.kastatic.org и *.kasandbox.org разблокированы.

Основное содержание

Перебор делителей

Постановка задачи

Нам необходимо создать некий автомат, который сможет ответить «да» или «нет» на простейший вопрос: является ли некое число n простым?
Давайте подумаем, как может быть устроен такой автомат. Автоматы умеют выполнять последовательность шагов, основываясь на инструкции, называемой алгоритмом. Для начала давайте узнаем, как работает такой алгоритм у вас в голове. Ответьте на вопрос: является ли число 49 простым?
Нет? Как вы это сделали? Вы вероятно искали делитель 49, который больше чем 1 и меньше чем 49. Если вы не помните таблицу умножения, то вам придётся буквально проделать следующие шаги:
  • Делится ли 49 на 2? НЕТ
  • Делится ли 49 на 3? НЕТ
  • Делится ли 49 на 4? НЕТ
  • Делится ли 49 на 5? НЕТ
  • Делится ли 49 на 6? НЕТ
  • Делится ли 49 на 7? ДА
Мы нашли делитель числа 49 (7), что доказывает, что число 49 составное.

Строительство стены

А если я вас спрошу: является ли число 2971215073 простым?
Вы всё ещё проверяете? Я перебрал первые несколько тысяч чисел — и так и не нашёл делителя. Здесь встаёт ключевой вопрос: в какой момент можно остановиться и точно сказать, что n — простое? (назовём этот момент стеной) Мы сразу можем сказать, что стена должна стоять не дальше n-1 (поскольку n делится на n). Если мы переберём 2971215072 чисел, тогда мы либо найдём делитель (тем самым докажем, что n составное) ИЛИ не найдём (тем самым докажем, что n простое).

Постройка более эффективной стены

Это действенный метод, но можем ли мы сдвинуть стену для экономии времени? Помните: мы фактически ищем первый (то есть наименьший) делитель. Иногда таким наименьшим делителем может оказаться число 2, а может оказаться и гораздо большее число. И тут мы подходим к ключевому вопросу: насколько большим может быть наименьший делитель?
Как вы помните, любое составное число n можно представить в виде произведения двух или большего количества простых чисел n= P * P …
P будет наибольшим, когда у n есть ровно два делителя, которые при этом равны друг другу. Такое число называют полным квадратом. Примерами полных квадратов могут быть 9 (9 = 33) или 49 (49 = 77). Таким образом, даже в самом «плохом» случае нам достаточно поставить стену рядом с квадратным корнем из n!
Убедитесь в этом сами: если мы не нашли делителя числа n, перебрав все числа до квадратного корня из n, значит, n — простое число. Попытайтесь доказать это утверждение (доказательство приведено внизу статьи)

Метод перебора делителей

Вот и всё, мы готовы двигаться дальше. Но сначала сформулируем обычным языком алгоритм перебора делителей:
  • Возьмём некое целое число n
  • Для каждого целого числа x из диапазона {2 ... sqrt(n)} проверим, делится ли n на x
  • Если делитель найден, то n составное, ИНАЧЕ n простое
Если вы умеете программировать, можете открыть наш специальный блокнот и запрограммировать этот алгоритм. Если нет, можете перейти к следующему шагу, где я покажу вам работающую версию, с которой вы можете начать. (Имейте в виду, что этот урок можно пройти вообще без программирования).

Хотите присоединиться к обсуждению?

Пока нет ни одной записи.
Знаете английский? Нажмите здесь, чтобы увидеть обсуждение, которое происходит на английской версии сайта.