Вопрос по теории чисел
Хм... Возможно, я не вполне понял вопрос...
Решето Эратосфена вполне можно использовать для
проверки N на простоту (другое дело, что есть алгоритмы и получше).
Если N простое, то для того чтобы это выявить, алгоритм придется
выполнять полностью - до [N^(1/2)]. Если же N - составное, то,
конечно же, оно будет вычеркнуто раньше, чем доберемся
до этой границы.
Если вопрос был в том, насколько раньше это произойдет при составном N,
то от моего ответа пользы не так много...
|