まずは \(1.5 \times 10^6\) 程度以下の数をすべて素因数分解して, 素因数を計算しておく. (べき乗は要らない) \(1.5 \times 10^6\) 以下には約 \(1.1 \times 10^5\) 個の素数があるので, ここまで計算しておけば十分だろう. \(1.5 \times 10^6\) 以下の素数をあらかじめ計算しておけばさらに高速化できる. なお, \(1.5 \times 10^6\) 以下であれば素因数の数は高々7である.

続いて \(b_i\) の計算であるが, あらかじめ \(b_j\ (j \lt i)\) で使われた素因数は記録しておく. そして考えられる最小値(*)が素因数が記録された素因数を含んでいれば \(1\) を加えた値を調べる. 以下これを繰り返して \(b_j\) と互いに素となる数を見つける. 素数は必ず \(b_j\) と互いに素となるので, そこまで多くの数を調べる必要はないだろう.

(*) 考えられる最小値は以下の通りである.

  • \(b_j = a_j\ (j \lt i)\) であれば \(a_i\)
  • \(b_{i-1} > a_{i-1},\ b_j = a_j\ (j \lt i-1)\) であれば \(2\)
  • そうでなければ \(b_{i-1}\)