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

Из Википедије, слободне енциклопедије

У математици Ератостеново сито је поступак за одређивање простих бројева мањих од неког задатог броја n. Креирао га је Ератостен, старогрчки математичар.

Алгоритам[уреди]

  • 1. Напишите све бројеве од 2 до n
  • 2. Почевши од првог броја на списку (двојка) прецртајте са списка све бројеве дељиве са два и упишите да је двојка прост број.
  • 3. Понављајте поступак са следећим непрецртаним бројем m. Дакле, прецртајте све бројеве дељиве са m, а њега самог обележите да је прост.

Напомена: Постоје ефикаснији алгоритми за проверу да ли је неки одређени број прост. Ератостеново сито налази све просте бројеве до неког броја.

Модификација[уреди]

  • 1. Из разматрања можемо избацити парне бројеве веће од 2 јер су сви они сложени. Тако је први број чије садржаоце тражимо 3, а не 2.
  • 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, ...

Animation Sieb des Eratosthenes.gif