Question

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

Answer 1

Ответ:

7

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

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

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

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

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

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

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

Answer 2

Алгоритм, описанный в видеолекции, для проверки простоты числа заключается в том, чтобы проверить его делители до квадратного корня этого числа. Если число 127 не делится на какое-либо число п, где п является простым числом и меньше или равно квадратному корню из 127, то можно утверждать, что 127 является простым числом.

В данном случае нужно найти все простые числа п, которые меньше или равны квадратному корню из 127 и проверить, делится ли 127 на каждое из этих чисел. Если 127 не делится ни на одно из таких чисел, то можно сделать вывод, что 127 является простым числом.

Квадратный корень из 127 примерно равен 11.27, поэтому достаточно проверить делители от 2 до 11. Проверяя все числа п от 2 до 11, Пете нужно убедиться, что 127 не делится на ни одно из этих чисел, чтобы утверждать, что 127 является простым числом.