Основное содержание
Информатика
Course: Информатика > Модуль 2
Урок 6: Тест простоты- Введение
- Пройди испытание на тест простоты
- Перебор делителей
- Чем ограничена память компьютера?
- Эффективность алгоритмов
- Уровень 3. Испытание
- Решето Эратосфена
- Уровень 4. Решето Эратосфена
- Тест простоты при помощи решета Эратосфена
- Уровень 5. Перебор делителей при помощи решета Эратосфена
- Теорема о распределении простых чисел
- Скатерть Улама
- Промежутки между простыми числами
- Компромисс времени и памяти
- Итоги (что дальше?)
Перебор делителей
Постановка задачи
Нам необходимо создать некий автомат, который сможет ответить «да» или «нет» на простейший вопрос: является ли некое число 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 простое
Если вы умеете программировать, можете открыть наш специальный блокнот и запрограммировать этот алгоритм. Если нет, можете перейти к следующему шагу, где я покажу вам работающую версию, с которой вы можете начать. (Имейте в виду, что этот урок можно пройти вообще без программирования).
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.