競プロ典型90問 075

Magic For Balls（★3）

星3の問題だが、

Nを素因数分解した時に√(N)を超える素数は高々単独の1つしかない

という高度な（？）法則を使っているのでその確認をする。

カウントの仕方だが、8の場合は2と2と2という風に各2を別のものとして3つとカウントする。

Nを素因数分解した結果、素数1つ

つまりN自体が素数のとき√(N)を超える素数はひとつ

Nを素因数分解した結果、素数2つ

2つの素数をa, bとする(a ≥b)

a=bのとき

√(ab)より大きな素数はなし

a>bのとき

√(ab)より大きな素数はa

Nを素因数分解した結果、素数3つ以上

素数を大きい方からをa, b, c, d…(a≥b≥c≥d…)とする。

先ほど見たように、a, bの中で√(ab)より大きな素数は高々ひとつ。

a*b*c*d…は、a*bに値が2以上のc*d…が加わることにより

√(a*b*c*d…)>√(ab)

よって√(a*b*c*d…)=√(N)を超える素数は高々ひとつ

図で全パターン書こうかと思ったけどだいたいの部分が同じなので省く。