Ератостеново сито
Прејди на прегледникот
Прејди на пребарувањето
Во математиката, Ератостеновото сито е едноставен и стар алгоритам за пронаоѓање на сите прости броеви до одреден цел број. Ситото е предходник на модерното „сито на Аткин“, кое е побрзо но посложено. Било осмислено од Ератостен, математичар од Стара Грција.
Алгоритам[уреди | уреди извор]
Алгоритамот се состои од шест чекори:
- Се пишува листа почнувајќи од бројот 2 (како прв прост број) па сè до бројот кој сакаме да провериме дали е прост. Оваа листа ќе ја наречеме A.
- Во друга се пишува бројот 2. Во оваа листа се запишуваат најдените прости броеви. Оваа листа ќе ја наречеме B.
- Се прецртува (прешкртува) бројот 2 и сите броеви во листата A кои се деливи со 2.
- Првиот непрецртан број на листата е прост број. Овој број се запишува во листата B.
- Се прецртува и овој број од листата A. Може да се започне со прецртувањето на броевите деливи со овој број, почнувајќи од квадратот на истиот број, бидејќи помалите делители веќе се прецртани.
- Се повторуваат ги чекорите 4 и 5 додека не се заврши со броевите во листата A.