прости числа - сито на Ератостен

Алгоритъмът за търсене на прости числа със сито на Ератостен има дълга история. Дава добри резултати за извеждане на всички прости числа от 2 до търсеното. На всеки цикъл се елиминират всички числа кратни на начално избраното. Алгоритъмът е известен като сито на Ератостен или решето на Ератостен или само решето. Името е следствие на използваното нагледно доказателство. В началото, на пергамент,  са написани всички естествени числа, избира се първото просто число (най-малкото е 2) и в цикъл се перфорират всички числа кратни на 2. Търсенето продължава с най-близкото неперфорирано число (това е 3) и отново в цикъл се перфорират всички числа кратни на избраното. Алгоритъмът продължава до достигане на последното неперфорирано числа. Като имплементация е удобно да се работи с масив от булев тип или предпочитана динамична структура.

Напишете изходен (сорс) код на програма, чрез която се въвежда естествено число N [12..1000001] и се извеждат всички прости числа от 2 до въведеното. Програмата да използва две аналогични функции - рекурсия и итерация. 

Като алгоритъм за търсене на прости числа в интервал да се използва сито на Ератостен.

Пример: 15 Изход: 2,3,5,7,11,13 .

Разгледайте други основни типове примерни задачи, за чието решение се използват прости числа и числови редици. Прочетете допълнителен материал за: прости числа в интервал. Сходен алгоритъм със сито на Ератостен бихте открили и в числа Ludic, щастливи числа.