a010: 因數分解
編輯歷史
| 時間 | 作者 | 版本 |
|---|---|---|
| 2017-07-19 14:10 – 14:10 | r0 – r1 | |
顯示 diff-
+ a010: 因數分解
+ http://zerojudge.tw/ShowProblem?problemid=a010
+ *MAX=1000000 # MAX=400000可以0.2秒AC，但那只是因為測資，大於400000的都不是質數
+ *is_prime=[False,False]+[True]*(MAX-1)
+ *primes=[]
+ *now=2
+ *while True:
+ * primes.append(now)
+ * for i in range(now*2,MAX+1,now):
+ * is_prime[i]=False
+ * now+=1
+ * try:
+ * while is_prime[now]==False:
+ * now+=1
+ * except:
+ * break
+ *
+ *while True:
+ * try:
+ * N=int(input())
+ * factorization=''
+ * for prime in primes:
+ * power=0
+ * while True:
+ * Q=N/prime # 只/一次，而不是%一次再/=一次
+ * if Q!=int(Q):
+ * break
+ * power+=1
+ * N=Q
+ * if power==1:
+ * factorization+=str(prime)+' * '
+ * elif power>1:
+ * factorization+=str(prime)+'^'+str(power)+' * '
+ * if N==1: # 測資分解到1就不再用後面的質數試圖因數分解了，可以省掉大量多此一除的除法運算時間
+ * break
+ * print(factorization[:-3])
+ * except:
+ * break
|
||