Ератостеново сито
Во математиката, Ератостеновото сито е едноставен и стар алгоритам за пронаоѓање на сите прости броеви до одреден цел број. Ситото е претходник на модерното „сито на Аткин“, кое е побрзо но посложено. Било осмислено од Ератостен, математичар од Стара Грција.[1]
Алгоритам
уреди
Алгоритамот се состои од шест чекори:
- Се пишува листа почнувајќи од бројот 2 (како прв прост број) па сè до бројот кој сакаме да провериме дали е прост. Оваа листа ќе ја наречеме A.
- Во друга се пишува бројот 2. Во оваа листа се запишуваат најдените прости броеви. Оваа листа ќе ја наречеме B.
- Се прецртува (прешкртува) бројот 2 и сите броеви во листата A кои се деливи со 2.
- Првиот непрецртан број на листата е прост број. Овој број се запишува во листата B.
- Се прецртува и овој број од листата A. Може да се започне со прецртувањето на броевите деливи со овој број, почнувајќи од квадратот на истиот број, бидејќи помалите делители веќе се прецртани.
- Се повторуваат ги чекорите 4 и 5 додека не се заврши со броевите во листата A.
Наводи
уреди- ↑ Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," Philosophical Transactions (1683–1775), Vol. 62. (1772), pp. 327–347.