Решето на Ератостен
от Уикипедия, свободната енциклопедия
„Решето на Ератостен“ е алгоритъм за намиране на всички прости числа в интервала [1, n], където n е произволно естествено число.
[редактиране] Алгоритъм
Записваме всички числа от 1 до n. Зачеркваме числото 1. Следващото число е 2 и то е просто. Подчертаваме 2 и зачеркваме през едно всички числа след 2. Това са именно числата, които се делят на 2 и следователно не са прости. Първото незачеркнато число е 3 и то е просто. Подчертаваме 3 и зачеркваме през две всички числа след 3. Те не са прости понеже са кратни на 3. Търсим първото незачеркнато число. То се оказва 5 и е просто. Продължавайки по същия начин ще получим последователно всичките прости числа от 1 до n.
Тази статия се нуждае от подобрение.
Ще отбележим още, че ако р е просто число и а е произволно друго число, то (а,р)=1, или (а,р)=р. Наистина ако означим d =( a , p ), то d дели р, от където следва, че d = 1 или d = p.
