分数を小さい順に保存するデータ構造を考えます。C++ならば以下のように実装することができます。

using P = pair<int,int>;
priority_queue<P,vector<P>,function<bool(P,P)>> que([](P a,P b){return a.first*b.second>a.second*b.first;});

次に、このデータ構造に \(\frac{1}{2},\frac{1}{3}, \cdots , \frac{1}{M}\) を入れます。また、配列 \(v\) を \(v[i]=1\) で初期化します。

その後、各分母についてどこまでの分子を見たかを管理する要領で以下の操作を繰り返すことで、分数を小さい順に取り出すことができます。

データ構造に入っている最小の分数を取り出す。取り出された回数がちょうど \(k\) 回ならこれを出力し操作を終了する。
取り出した分数の分母 \(z\) について \(v[z]\) に \(1\) を足し、その後 \(v[z]\) を \(z\) と互いに素になるまで \(1\) を足す。 次に、 \(v[z] < z\) ならば \(\frac{v[z]}{z}\) をデータ構造に入れる。