На вход программе подается натуральное число n <= 109. проверьте, является ли оно простым. выведите yes или no в зависимости от ответа на вопрос задачи. максимальное время работы программы на одном тесте — 0,1 секунды.

Для решения задачи проверки числа на простоту при $n\le {10}^9$ и ограничении времени 0,1 секунды наиболее эффективным методом является проверка делителей до $\sqrt{n}$ . Сложность такого алгоритма составляет $O\left(\sqrt{n}\right)$ , что при максимальном $n$ дает около $31,622$ итераций — это значительно меньше допустимого лимита времени. Шаг 1: Обработка краевых случаев Число $n<2$ по определению не является простым. Если на вход подается $1$, программа должна сразу вывести no. Для $n=2$ программа должна вывести yes, так как это единственное четное простое число. Шаг 2: Оптимизация перебора делителей Вместо перебора всех чисел до $n$, достаточно проверить делители в диапазоне от $2$ до $\lfloor \sqrt{n}\rfloor$ . Если число $n$ составное, то оно обязательно имеет хотя бы один делитель $d$, такой что $d\le \sqrt{n}$ . Если ни одного такого делителя не найдено, число является простым. Шаг 3: Реализация алгоритма Для повышения скорости можно отдельно проверить делимость на $2$, а затем в цикле проверять только нечетные числа с шагом $2$. Однако при $n={10}^9$ обычного цикла до корня будет достаточно для соблюдения лимита в 0,1 сек. Пример кода на Python: n = int(input()) if n < 2: print("no") else: d = 2 is_prime = True while d * d <= n: if n % d == 0: is_prime = False break d += 1 print("yes" if is_prime else "no") Ответ: Для проверки числа $n\le {10}^9$ на простоту в пределах 0,1 секунды необходимо использовать алгоритм с временной сложностью $O\left(\sqrt{n}\right)$ . Программа должна проверять наличие делителей в интервале $[2;\sqrt{n}]$ . Если хотя бы один делитель найден, выводится no, в противном случае — yes. Нужно ли вам оптимизировать этот алгоритм для одновременной проверки множества чисел (например, с помощью решета Эратосфена)?