Проверка, является ли число простым — немного быстрее
Предположим, у крупной компании уже есть программа, которая проверяет, является ли число простым. Однако компания быстро растёт, число пользователей стремительно увеличивается, и вместе с этим возрастает нагрузка на ваш код. Вас просят оптимизировать программу и сделать её чуть быстрее, чтобы она справлялась с растущим потоком новых пользователей.
Вероятнее всего, ваше предыдущее решение выглядело так:
- Перебирать все числа от 2 до
nи подсчитывать количество делителей.
- Перебирать все числа от 2 до
nи останавливать проверку при обнаружении первого делителя.
Существует несколько небольших улучшений, которые помогут оптимизировать эту процедуру:
Optimization 1:
Вместо того чтобы проверять все числа от 2 до
n, можно сначала проверить, делится ли n на 2, а после этого рассматривать только нечётные числа. Если число на 2 не делится, то проверять все остальные чётные числа (4, 6, 8, 10, 12 и т. д.) уже нет необходимости.Optimization 2:
Вместо перебора чисел от 2 до
n, достаточно идти максимум до n/2, так как наименьший возможный делитель равен 2 ⇒ не найдётся ни одного делителя больше, чем n/2.Мы можем совместить эти два подхода. Тогда для проверки останутся только нечётные числа до
n/2. Получится около n/4 таких кандидатов, а значит, код будет работать примерно в четыре раза быстрее по сравнению с наивным перебором всех чисел подряд.Несмотря на то, что такие оптимизации действительно ускоряют программу, с точки зрения асимптотической сложности всё остаётся по-прежнему линейным. Когда
n растёт, число операций растёт пропорционально ему. О том, как радикально уменьшить объём работы при проверке числа на простоту, мы поговорим позже.Входные данные
Первая строка содержит одно целое число
n (1 ≤ n ≤ ).Выходные данные
Программа должна вывести
Yes, если n — простое число, и No в противном случае.Примеры
Input | Output |
8 | No |
7 | Yes |
1 | No |
19 | Yes |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB