Вопрос по теории чисел
vega
Я говорил только о выделении простых чисел в заданном ряде
натуральных чисел от 1 до N, путем вычеркивания составных,
с помощью решета Эратосфена - наиболее простого метода.
Вопрос проверки на простоту не ставился. Вопрос касается
только именно решета Эратосфена: до каких пор заниматься
отсеиванием. Причем сам ряд натуральных чисел от 1 до N
может быть задан для произвольного N, вовсе необязательно
только простого. N - может быть любым натуральным числом.
Не спешите так аппелировать к кажущимся очевидностям.
Нужно строгое доказательство следующего утверждения:
Для того, чтобы при любом натуральном N в ряде натуральных
чисел от 1 до N можно было вычеркнуть все составные числа,
необходимо и достаточно провести последовательное отсеива-
ние чисел кратных q = 2,3,..., [N^0.5], за исключением самих q.
|