ABC096 D Five, Five Everywhere 解説 - hinamelプログラミングメモ

・55555以下の素数がN個(5<=N<=55)ある。

・N個のうち、どの5つを取っても合成数(素数でない数)となり、さらにN個全ての数がそれぞれ異なる。このようなN個の素数の組み合わせを求める。

・合成数ということは、2つ以上の素数の積で表せる数ということになる。例えば、ある素数の倍数はその数自身を除いてすべて合成数になる。

・また、この数列の最小値は2+3+5+7+11 = 28となる。

・5つの素数の和を合成数にするには、5つの素数の和がある数の倍数になればいいことに気が付く。例えば、5で割って1余る素数を5つ集めれば、かならず和は5の倍数となる(=合成数となる)。これを実装すればよい。

・素数はエラトステネスの篩を実装して求める。

体感難易度:☆4

・気づくとスカッとする問題だった。余りをかきあつめて一つの倍数を作るイメージを使う時もあることを覚えておく。