Для того, чтобы проверить чисто на простоту, достаточно переделить его на все числа до его арифм. квадратного корня?

Question

Типа, есть число 257. Чтобы проверить, что оно простое, достаточно поделить его на 2, 3, 4, 5, 6, 7, 8, 9, 14, 15, 16? После 16 проверять не имет смысла, да? (16 - округленный до целых арифм. квадратный корень от 257)

Заране спасибо за ответ

Answer 1

Можно ещё сократить, проверив делимость на 6n (+-) 1. Простое всегда имет вид 6n или 6n-1. Идею можно продолжить.
Ещё лучше - на все простые, меньшие квадратного корня. Но их список надо иметь.

Answer 2

Вобще-то делить на простые числа, если узнать простоту их несложно. В данном примере достаточно делить на 3 (исходное число 257 нечётное и потому делить на 2 нет смысла) , 7 (не заканчивается на 5 и потому делить на него нет смысла) , 11 (перешагнули 3, т. е. на 3 не делится; потому делить на 9 нет смысла) и 13 (делить на 15 нет смысла, ибо перешагнули 3 и 5) .
Таким образом, в данном примере достаточно проверить на делимость на 3, 7, 11 и 13.