Чтобы узнать, является ли число 1601 простым, его стали последовательно делить на 2, 3, 5 и т. д. На каком простом числе можно прекратить испытания?

1) Единицу не удосужились признать простым числом. Её пропускаю.
Все простые чисел с 2 по 40: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Почему по 40? Извлеку корень из 1601. Число, умноженное само на себя большего не будет. Корень из 1600 будет 40.
2) Пополам делятся только чётные числа, а 1601 нечётное.
3) Признак делимости на 3 - сумма цифр должна делиться на три, а тут 8. Не подходит.
5) У пятёрке в разряде единиц должен быть нуль или пять, а у числа 1601 - единица. Не подходит.
7) Числа разряда единиц нужно умножить на два. Полученное произведение отнять от оставшегося числа без неё. Что получится должно делиться на 7. 160 - 2 = 158. Не делится. Не подходит.
11) Делится на 11 только в том случае если сумма чётных цифр равна сумме нечётных цифр или разница в 11. 7 - 1 = 6. Не подходит.
13) Как и у семёрки только надо умножать не на два, а на девять:
160 - 9 = 151. 15 - 9 = 6. Не подходит.
17) Как и у семёрки и у 13, только надо умножать на 5:
160 - 5 = 155. 15 - 25 = -10. Не подходит.
19) Тоже самое, но последнюю цифру надо умножить на 2:
160 - 2 = 158. Не делится. Не подходит.
23) Тоже самое, но надо умножить на три:
160 - 3 = 157. 15 - 21 = -6. Не подходит.
29) Мне не известен признак делимости на 29. Разделю на калькуляторе. Не подходит.
31) Мне не известен признак делимости на 31. Разделю на калькуляторе. Не подходит.
37) Мне не известен признак делимости на 37. Разделю на калькуляторе. Не подходит.
Всё! Число 1601 простое. Моё доказательство выше.
                                                                              

Достаточно прекратить процесс деления на последовательные простые числа на простом числе, непревышающем целой части корня из проверяемого числа n.
Допустим, проверена делимость n на числа d<=floor(sqrt(n)), где floor(.) -- взятие целой части, sqrt(.) -- квадратный корень. Если число n делится на d>floor(sqrt(n)) то результат n/d такого деления будет меньше [целочисленного] корня из n, т.е. n/d < floor(sqrt(n)), но все эти числа уже были проверены по предположению.
В данном конкретном случае, floor(sqrt(1601)) = 40 -- число составное, врочем как и ближайшие меньшие его числа 39 и 38, а вот число 37 -- простое и именно проверкой делимости 1601 на 37 достаточно завершить процесс проверки 1601 на простоту (подсказка: число 1601 не делится на простые числа, непревышающие 37).

При проверке числа на простоту имеет смысл проверять делители только от 2 до квадратного корня из числа.
Докажем это методом от противного.
Предположим, что наше число N имеет два делителя a и b:
N = a*b
Причем √N < a < b
То есть оба делителя больше, чем квадратный корень из нашего числа N.
Но тогда их произведение:
a*b > √N*√N
a*b > N
А по условию произведение a*b = N.
Пришли к противоречию. Значит, наименьший делитель не может быть больше, чем √N.
В нашем случае N = 1601, √N = 40,01, поэтому имеет смысл проверять простые числа от 2 до 40:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.
Разделив 1601 на каждое из этих чисел, мы не получим ни одного целого результата.
Это означает, что число 1601 - простое.