AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の75問目である「075 – Magic For Balls（★3）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【075 – Magic For Balls（★3）】
問題概要
整数 \(x\) が書かれたボールがあり、そのボールを叩くことで特定の操作が行われます。目的は、整数 \(N\) が書かれたボールを叩いて、すべてのボールに書かれている数を素数にすることです。このとき、最小で何回の操作を行う必要があるのかを求める問題です。
考察
整数 \(x\) を叩くと、 \(x\) が素数でない場合、 \(x\) を2つの因数 \(a\) と \(b\) に分けることができます。この操作を繰り返すことで、最終的にすべてのボールに書かれている数を素数にすることが目的です。
この操作の特徴として、最大の因数の数は \(2^{\text{作業回数}}\) となります。これは、1回の操作でボールの数が最大2倍になるためです。
したがって、最初に整数 \(N\) の因数の数を求め、その因数の数が \(2^{\text{作業回数}}\) 以下となる最小の作業回数を求めることで、答えを得ることができます。
因数となる\(a\), は必ず\(\sqrt{N}\)以下ですので、探索する範囲は\(O(\sqrt{N})\)ですので、十分高速に答えが求まります。
コード
def tameshi(n):
ret = []
for i in range(2, int(n ** (1 / 2)) + 1):
if i > n:break
while n % i == 0:
n //= i
ret.append(i)
if n != 1:
ret.append(n)
return ret
n = int(input())
prime_cnt = len(tameshi(n))
cnt = 0
while True:
if 2**(cnt) >= prime_cnt:
print(cnt)
break
else:
cnt += 1
コメント