Проверка числа на простоту – быстрый метод
До сих пор, чтобы узнать, является ли число
n простым, мы фактически перебирали делители в линейном порядке. Это означает, что если мы увеличим n, количество операций для определения его простоты будет возрастать пропорционально (с некоторым множителем). Таким образом, если рассматривать худшие случаи (все ситуации, когда число n само по себе простое — 51, 107 и т.д.), наш алгоритм выполнял примерно n/4 операций при проверке n на простоту.Из этого следует, что при увеличении
n в 10 раз алгоритм будет работать в 10 раз дольше. Если увеличить n в 100 раз, алгоритм будет работать в 100 раз дольше. То есть производительность нашего алгоритма прямо пропорциональна n. Можно ли проверять число быстрее? Кажется, что в нашем подходе есть много лишних проверок.Метод :
Предположим, у числа
n есть делитель d.Это значит, что
n делится на d без остатка, и при этом и d, и — целые числа. Более того, либо d, либо меньше либо равно . Следовательно, при проверке на простоту мы можем ограничиться перебором делителей только до вместо . Нас интересует, делится ли наше число на любой делитель, кроме 1 и самого n, поэтому мы фокусируемся на меньшем из d и . А раз один из них обязательно меньше , мы можем ограничить цикл проверки значениями до и остановиться.Это колоссальное улучшение! Выполнять операций вместо
n — огромная экономия. Представьте себе алгоритм, которому понадобилось бы 10 лет (3650 дней) на вычисление. При оптимизации на основе ему потребовалось бы всего 2 месяца (61 день).Существуют ли более эффективные алгоритмы для проверки числа на простоту?
Да! Подробнее об этом можно прочитать в Algorithms for Competitive Programming. Некоторые алгоритмы увеличивают количество операций (по мере роста
n) логарифмически, а не пропорционально .Ввод
Первая строка содержит одно целое число
n (1 ≤ n ≤ ).Вывод
Программа должна вывести
Yes, если n является простым, и No — в противном случае.Примеры
Input | Вход |
1 | No |
11 | Yes |
353557 | Yes |
34134741 | No |
902468477 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB