Доброго времени суток, товарищи! Сегодня речь пойдет в продолжение предыдущей темы, а именно, мы будем писать Решето Эратосфена за линию. Те, кто не знаком с оригинальным решетом - сюды. Основная проблема Эратосфена в том, что мы помечаем составные числа по несколько раз, наша задача состоит в том, чтобы как-то помечать числа только по разу. Предположим, что мы знаем минимальный простой делитель какого-то произвольного числа, k - p[k]. и, если мы будем домножать k на простые числа до p[k] (p[j]), то мы однозначно получим число, у которого наименьший простой делитель p[j]...

Доброго времени суток, товарищи! Сегодня я продолжу речь про простые числа, а именно, расскажу про Решето Эратосфена. Когда-то давным-давно древнегреческому математику Эратосфену Киренскому пришла в голову одна замечательная идея, который мы пользуемся и по сей день. Суть состоит в том, чтобы находить все простые числа до какого-то заданного n, вычеркиванием составных чисел. *составное число - число, которое можно представить в виде с = a*b, где ни a ни b не являются 1* Представим, что мы уже знаем, что 2 (первое простое число) - простое число...