---
tags: python,prime,質數
---

# ZJ d120. 10699 - Count the factors
[ZJ d120](https://zerojudge.tw/ShowProblem?problemid=d120)

nlist:標記0~n，是否為質數
plist:質數清單

## 思考流程圖

graph TD;
建立0-n的質數表plist及nlist-->處理輸入值=nt=ni;
處理輸入值=nt=ni-->由nlist判斷-->nt非質數-->逐一plist因式分解ans+1-->輸出結果;
由nlist判斷-->nt為質數-->ans=1-->輸出結果;
輸出結果-->結束;

## 程式流程圖

st=>start: 開始
op=>operation: 建立0-n的質數表plist及nlist
input=>inputoutput: 處理輸入值=nt=ni
op2=>operation: 逐一p in plist因式分解
ans+1
result=>inputoutput: 輸出結果
cond=>condition: 由nlist判斷
nt是否質數?
cond2=>condition: 判斷nt=0?
e=>end: 結束

st->op->input->cond2
cond(yes)->result
cond(no)->op2->result
result(left)->input
cond2(yes,right)->e
cond2(no)->cond

## code
AC (0.8s, 14.9MB)

#線性篩法質數建表
n=1000000
nlist = [0,0,1]
for i in range(n//2):
    nlist += [1,0]
plist = [2]
for i in range(3,n,2):
    if nlist[i]:
        plist.append(i)
    for pi in plist:
        if pi*i>n: break
        nlist[pi*i] = 0
        if i % pi ==0: break

while True:
    try:
        ni = nt = int(input())
        if nt == 0: break
        if nlist[nt]: #先判斷是否為質數，可加快0.2 S
            ans = 1
        else:
            ans = 0
            for p in plist:
                if nt % p == 0:
                    ans += 1
                    while nt % p == 0: #質因數分解，可加快0.2 S
                        nt //= p
                    if nt == 1:break
        print('{} : {}'.format(ni,ans))
    except EOFError:
        break

###### tags: `質數` `python` `prime`