競プロ典型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) を超える素数は高々ひとつ

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