素因数分解を利用せよ！ ABC169 D問題「D - Div Game」

こんばんは Ruteです。
AtCoder Beginner Contest 169のD問題「D - Div Game」をACしましたので、
私がACをした解法の説明をしていきたいと思います。

ABC169 - D問題「Div Game」

問題概要:

正の整数$N$が与えられます。$N$に対して以下の操作を繰り返し行うことを考えます。
以下の条件を満たす正の整数$z$を選ぶ。
・ある素数$p$と正の整数$e$を用いて $z = p^e$と表せる
　　・$N$が$z$で割り切れる
　　・以前の操作で選んだどの整数とも異なる
・$N$を、$N/z$に置き換える
最大で何回操作を行うことが出来るかを出力せよ。

解法:

問題文を見ると、$N = p_1^{1} × p_1^{2} × p_1^{3}×...$
というように素因数分解できると考え、以下のアルゴリズムを考えました。
・$N$を素因数分解した結果をリストlsとおく。
・lsにおけるそれぞれの素数について、1連続・2連続... $k$　($k$は自然数)連続しているかを見る。(ここで、1連続という言葉はないですが、分かりやすくするためにこのように表現しています)
例えば、24の場合 $24 = 2×2×2×3$です。
2は、1連続　した後に　2連続　しています。よって$N$が$2,4$で割り切れるから2回操作ができることになります。

3は、要素が1つしか無いです。よって$N$が2,4で割った後に3で割り切れるから
1回操作ができることになります。

操作の回数を合計すると、3回となります。

これでは分かりにくいので、もう少し抽象的な言い方をすると、

lsにおけるある素数の要素$ls_i$について、その要素の個数を$A$とおくと、
$\sum_{k =1}^{X}k ≦ A <\sum_{k =1}^{X+1}k$
を満たす$X$がその素数に対する操作回数となります。
例えば、$ls_i$が3回連続していれば2回操作出来、$ls_i$が54回連続していれば9回操作できる　といった感じです。
あとは、これを実装すればよいです。

ACしたコード

D.py

import math
def prime_diviation(n):
    factors = []
    i = 2
    while i <= math.floor(math.sqrt(n)):
        if n%i == 0:
            factors.append(int(i))
            n //= i
        else:
            i += 1
    if n > 1:
        factors.append(n)
    return factors
N = int(input())
#素因数分解
ls = prime_diviation(N)
now = 0 #現在参照する数字
ren = 0 #連続している数
target = 2 #連続している数の目標
ans = 0 #割り切れる回数
for i in range(len(ls)):
    if i == 0:
        #はじめの処理
        now = ls[i]
        ans += 1
    else:
        #もしnowと同じなら
        if ls[i] == now:
            ren += 1
            if ren == target:
                ans += 1
                ren = 0
                target += 1
        else:
            #1連続は確定している
            ans += 1
            ren = 0
            target = 2
            now = ls[i]
print(ans)

以上、ABC 169 D問題「D - Div Game」について私が考えた解法の説明を終わります。

Qiita初心者なので、表現が若干変だったらすみません((
もし、この解法が役に立った！等と思った方はLGTMのボタンを押して頂けると嬉しいです！