Úloha: Množina $M$ obsahuje pouze taková přirozená čísla, která nejsou dělitelná jiným prvočíslem než $2$, $3$ a $5$. Vypište co nejrychleji prvních $n$ nejmenších čísel množiny $M$.

Řešení: První řešení, které člověka napadne, je procházet postupně všechna přirozená čísla a testovat, zda nejsou dělitelná jiným prvočíslem než $2$, $3$ a $5$. Nebudeme si vysvětlovat detaily tohoto řešení a raději si ukážeme daleko rychlejší řešení.

Řešení: Nejprve učiníme několik pozorování. Teprve v posledním odstavci si ukážeme, jak provést jednu iteraci algoritmu.

Množina $M$ obsahuje pouze čísla tvaru $2^i 3^j 5^k$, pro všechny možné indexy $i,j,k\geq 0$. Dejme tomu, že už jsme vypsali prvních $s$ čísel $m_1$, $m_2$, $m_3$, $\dots$, $m_s$ množiny $M$. Vydělením čísla $m_{s+1}$ jedním z čísel $2,3,5$ dostaneme menší číslo patřící do $M$, které už bylo vypsáno. Proto následující číslo $m_{s+1}$ dostaneme tak, že jedno z předchozích čísel $m_i$ pro $i\leq s$ vynásobíme buď $2$ nebo $3$ a nebo $5$.

Protože $m_1 < m_2 < m_3 < \dots$, tak i $2m_1 < 2m_2 < 2m_3 < \dots$. Najdeme si takový index $I$, že $2 m_i \leq m_s$ pro všechna ${i}<{I}$ a $2 m_i > m_s$ pro všechna $i\geq I$. Podobně pro čísla tvaru $3m_j$ a $5m_k$ najdeme indexy $J$ a $K$.

Následující číslo, které máme vypsat, je $m_{s+1}=\min\{\,2m_I, 3m_J, 5m_K\,\}$. Až ho vypíšeme, tak stačí posunout příslušný index o $1$. Tím nastavíme indexy $I$, $J$, $K$ na správnou hodnotu. Pro výpis dalšího čísla můžeme postup zopakovat.