python3 で素因数分解を行う方法を以下にご紹介します。
結果を辞書型で返し、計算量は O(N **(1/2)) です。

def factorization(n):
    dic = {}
    tmp = n
    for i in range(2, int( - (-n ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            dic[i] = cnt
    if tmp != 1:
        dic[tmp] = 1

    if len(dic) == 0:
        dic[n] = 1

    return dic

n = 36
dic = factorization(n)
print(dic)

少しでもお役に立てれば幸いです。