Петя решил проверить, что число 127 является простым. Он будет действовать...

Question

Петя решил проверить, что число 127 является простым. Он будет действовать согласно алгоритму, описанному в видеолекции. Для каких чисел п ему достаточно проверить, что 127 не делится на п, чтобы удостовериться, что число 127 простое?

Comments

надеюсь, все понятно объяснил

---

да, спасибо

Answer 1

Ответ:

7

Пошаговое объяснение:

Для проверки не нужно проверять все числа до данного. Достаточно проверить до числа, равного корню из данного. В данном случае это чуть более 11. Поэтому включим и 12

нужно проверить на делимость на числа от 2 до 12.

но четные проверять не имеет смысла, так как на них делятся только четные числа. Тройку, пятерку и девятку тоже не нужно по признакам делимости. Остается 7 и 11.

Но для 11 тоже есть признак делимости: 1+7-2=6 не делится на 11.

Поэтому нужно проверить только число 7.

Но все предыдущие нечетные проверяем быстро признаками делимости