Prakticky řešíme úlohu pomocí pole přirozených čísel, resp. booleovských hodnot. Prvek pole A[i]
má hodnotu 1, je-li číslo
i
prvočíslo, jinak má hodnotu 0. Na počátku inicializujeme prvky na hodnotu 1 (předpokládáme, že všechna čísla jsou prvočísla).
Pak přiřazujeme prvkům pole s indexy odpovídající násobkům čísel 2, 3 , ... , n/2 hodnotu 0. Algoritmus můžeme zrychlit tím, že
je-li A[j]=0
, již nenulujeme prvky s indexy odpovídající násobkům čísla i (jsou již vynulovány). Na závěr vypíšeme indexy prvků
pole, kde A[j]=1
.