Почему мы проверяем только квадратный корень простого числа, чтобы определить, является ли оно простым? Разве мы не можем использовать кубический корень?

Question

Если число n можно записать как axb и m = sqrt (n). Здесь n = m * m. Мы говорим, что нам нужно только проверять до m, потому что min (a, b) < = m. Так что, возможно, мы берем корни куба? Предположим, что мы берем n = 21, тогда n = 1x3x7. Но корень Куба - 2. Почему этот метод терпит неудачу?

Answer 1

Рассмотрим п = 143 = 11 * 13. Кубический корень из 143 находится между 5 и 6. Если вы только тест делимости на простые числа до 6, вы не найдете ни из двух факторов н и ошибочно заключают, что 143 является простым.