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

Из пројекта Википедија

У математици Ератостеново сито је поступак за одређивање простих бројева мањих од неког задатог броја 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, ...