close
Content
寫一個程式算出一個正整數有多少個不同的質因數。例如：45=3*3*5，所以45有2個質因數（3和5）。
Input
每組測試資料一列。含有1個正整數 n（ 1 < n <= 1000000）。
若 n=0 代表輸入結束。
Output
對每組測試資料輸出一列，n有多少個不同的質因數。輸出格式請參考Sample Output。
Sample Input #1
7 8 45 289384 930887 692778 636916 747794 238336 885387 760493 516650 641422 0
Sample Output #1
7 : 1 8 : 1 45 : 2 289384 : 3 930887 : 2 692778 : 5 636916 : 4 747794 : 3 238336 : 3 885387 : 2 760493 : 2 516650 : 3 641422 : 3
這一題也是難在要如何不超時
python:
"""這裡住要是建造質數表"""
max=100
f=[0,1]*(max//2+1)
f[0]=0;f[1]=0;f[2]=1;f[3]=1
sam=[]
h=int(max**0.5)
for i in range(3,h+1,2):
if(f[i]==1):
for j in range(i*i,max+1,i*2):
f[j]=0
#rint(f) """那這裡會變成[0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0,.....，把他變成數字形態"""
for i in range(len(f)):
if f[i]==1:sam.append(i)
#print(sam) """[2, 3, 5, 7, 11, 13, 17, 19, 23......"""
while True:
try:
n=int(input())
c=n
if n==0:break
ans=0 #計算數量用
for i in sam:
if i>n:break #這行一定要有
if n%i==0:ans+=1
while n%i==0 :n//=i
if n!=1:ans+=1 #可能是%到最後剩下他自己，所以+1
print(f'{c} : {ans}')
except:
break
文章標籤
全站熱搜
留言列表
{{ article.title }}