[zerojudge] d120: 10699 - Count the factors

from sys import stdin
import math  

'''
題目說 n <= 1000000
而  n 的質因數 <= sqrt(n)
所以先來建立一個質數表
'''
limit = 1000000
u = int(math.sqrt(limit))
sieve = [0, 0, 2, 3] + [1] * (u - 4)
prime = [2]
for i in range(3, u, 2):
    if(sieve[i] == 0): continue
    # sieve[i] 為 0 表示被篩掉了    
    prime.append(i)
    for j in range(i*i, u, i): 
        sieve[j] = 0
# 你可以 print(prime) 來核對
# print(prime)  

def 質因數計次(n):
    tmp = n
    res = 0
    k = math.sqrt(n)
    for pr in prime:
        if(pr > k): break
        # 檢查到 n 的平方根
        c = 0
        while(tmp%pr == 0):
            c = 1
            tmp //= pr
        res += c
        # c 是試除符合       
    if(tmp > 1): res += 1
    # 剩餘的數 > 1 必定是質因數
    return '{} : {}'.format(n, res)

opt = []
for s in stdin:
    n = int(s)
    if(n == 0): break
    opt.append(質因數計次(n))
    
print('\n'.join(opt))
# 一次輸出