Ератостеново сито
Из пројекта Википедија
У математици Ератостеново сито је поступак за одређивање простих бројева мањих од неког задатог броја n. Креирао га је Ератостен, старогрчки математичар.
[уреди] Алгоритам
- 1. Напишите све бројеве од 2 до n
- 2. Почевши од првог броја на списку (двојка) прекрижите са списка све бројеве дељиве са два и упишите да је двојка прост број.
- 3. Понављајте поступак са следећим не прекрижаним бројем m. Дакле, прекрижајте све бројеве дељиве са m, а њега самог обележите да је прост.
Напомена: Постоје ефикаснији алгоритми за проверу да ле је неки одређени број прост. Ератостеново сито налази све просте бројеве до неког броја.
[уреди] Модификација
- 2.б) Поступак крижања бројева почињемо од m² јер су сви бројеви мањи од m² већ избрисани.
- 3.б) Чим нађемо прост број m такав да је m²>n немамо потребу за даљим брисањем. Сви преостали бројеви су прости!
[уреди] Пример
- Желимо да нађемо све просте бројеве до 120. Напишемо на папир бројеве од 2 до 120.
- Двојка је прост број. Избришемо све парне бројеве.
- Следећи број на списку је тројка. Обележимо и њу да је проста. Са списка бришемо 9,15,21,27,...
- Следећи број на списку је петица. И то је прост број. Са списка бришемо 25,35,55,65,85,95,115
- Следећа нам је на списку седмица. У списку простих бројева имамо за сада 2,3,5 и 7. Бришемо са списка 49, 77, 91 и 119. Напомена: 56, 63, 70, 84, 98, 105 и 112 су већ раније избрисани.
- Следећи број је 11. Како је 11²>120 то обележавамо да су сви преостали бројеви прости. То су 11, 13, 17, 19, 23, 29, 31, 37, ...
