Умные вопросы
Войти
Регистрация
Для того, чтобы проверить чисто на простоту, достаточно переделить его на все числа до его арифм. квадратного корня?
Типа, есть число 257. Чтобы проверить, что оно простое, достаточно поделить его на 2, 3, 4, 5, 6, 7, 8, 9, 14, 15, 16? После 16 проверять не имет смысла, да? (16 - округленный до целых арифм. квадратный корень от 257)
Заране спасибо за ответ
4 года
назад
от
fermermen
2 Ответы
▲
▼
0
голосов
Можно ещё сократить, проверив делимость на 6n (+-) 1. Простое всегда имет вид 6n или 6n-1. Идею можно продолжить.
Ещё лучше - на все простые, меньшие квадратного корня. Но их список надо иметь.
4 года
назад
от
A B
▲
▼
0
голосов
Вобще-то делить на простые числа, если узнать простоту их несложно. В данном примере достаточно делить на 3 (исходное число 257 нечётное и потому делить на 2 нет смысла) , 7 (не заканчивается на 5 и потому делить на него нет смысла) , 11 (перешагнули 3, т. е. на 3 не делится; потому делить на 9 нет смысла) и 13 (делить на 15 нет смысла, ибо перешагнули 3 и 5) .
Таким образом, в данном примере достаточно проверить на делимость на 3, 7, 11 и 13.
4 года
назад
от
spark
Связанные вопросы
1
ответ
Как определить "стоячесть" электромагнитной волны вдоль провода? Назовите три метода как минимум, кто нас сегодня удивит
4 года
назад
от
Лапочка
3
ответов
подойдет ли к шуроповерту 12v аккамулятор на 18v?
10 года
назад
от
newdosug
2
ответов
Итоги второй мировой войны
4 года
назад
от
Shahin Hasanov