Решето на Ератостен

от Уикипедия, свободната енциклопедия

„Решето на Ератостен“ е алгоритъм за намиране на всички прости числа в интервала [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.