Ератостеново сито

Во математиката, Ератостеновото сито е едноставен и стар алгоритам за пронаоѓање на сите прости броеви до одреден цел број. Ситото е претходник на модерното „сито на Аткин“, кое е побрзо но посложено. Било осмислено од Ератостен, математичар од Стара Грција.^[1]

Алгоритам

Анимација на Ератостеновото сито

Алгоритамот се состои од шест чекори:

1. Се пишува листа почнувајќи од бројот 2 (како прв прост број) па сè до бројот кој сакаме да провериме дали е прост. Оваа листа ќе ја наречеме A.
2. Во друга се пишува бројот 2. Во оваа листа се запишуваат најдените прости броеви. Оваа листа ќе ја наречеме B.
3. Се прецртува (прешкртува) бројот 2 и сите броеви во листата A кои се деливи со 2.
4. Првиот непрецртан број на листата е прост број. Овој број се запишува во листата B.
5. Се прецртува и овој број од листата A. Може да се започне со прецртувањето на броевите деливи со овој број, почнувајќи од квадратот на истиот број, бидејќи помалите делители веќе се прецртани.
6. Се повторуваат ги чекорите 4 и 5 додека не се заврши со броевите во листата A.