n > 0 と n != 0 が違うだけでACかTLEが変わる原因
n > 0 と n != 0 の違い(速さなど)が知りたいです
AtCoderのABC280, D問題についてなのですが、以下のコードがなぜTLEになるのかを教えて下さい。
TLEになるコード
from collections import defaultdict
k = int(input())
cnt = defaultdict(int)
s = k
i = 2
while i*i <= k and s != 1:
while s%i == 0:
cnt[i] += 1
s //= i
i += 1
if s != 1:
cnt[s] += 1
ans = 1
for a, b in cnt.items():
j = 1
while b != 0:
n = a * j
while n%a == 0:
n //= a
b -= 1
j += 1
j -= 1
ans = max(ans, a*j)
print(ans)
ACとなるコード
from collections import defaultdict
k = int(input())
cnt = defaultdict(int)
s = k
i = 2
while i*i <= k and s != 1:
while s%i == 0:
cnt[i] += 1
s //= i
i += 1
if s != 1:
cnt[s] += 1
ans = 1
for a, b in cnt.items():
j = 1
while b > 0:
n = a * j
while n%a == 0:
n //= a
b -= 1
j += 1
j -= 1
ans = max(ans, a*j)
print(ans)
TLEのコードとACのコードの違い
20行目(下から10行)のところが
while b != 0:
while b > 0:
というだけです。
どうして、ここまで差が出るのかを教えてほしいです。
0