作者Lucemia (生の直感、死の予感)
看板Python
標題Re: [問題] 用Python算質數
時間Fri Apr 24 07:38:24 2009
※ 引述《leondemon (狗狗)》之銘言:
: 改自http://larc.ee.nthu.edu.tw/~jcyeh/python/cdoc/tut/node6.html
: code如下:那行
: ===========
: def primeNumber(x):
: for n in xrange(2,x):
: for m in xrange(2,n): #第二個for loop
: if n%m == 0:
: break
: else: #為何else要縮排在這裡?
: print n,
: x = int(raw_input("enter a number:"))
: primeNumber(x)
: ===========
: 當數字大於100000時 計算就耗時了
: 有辦法改code加速尋找質數的運算嗎?
^^^^^^^^
1. 尋找質數無有效的方式 (無多項式時間解)
2. 沒有有效的,但有很多種較好的解、
像是篩法、
這個範例寫的是直接照質數的定義、
是最不好的解。自然很慢。
但不管怎樣改、在大數下都不會快
(如將 xrange(2, n ) 改成 xrange(2, sqrt(n)) 都會好些)
3. for 的 else 與 if 的 else statment 不一樣
for 的 else 是拿來處理 break的 (文章內有寫)
用途就是只在for break時執行這些步驟、若for 正常執行就不做
下面這種情況較能感覺到這個用法的好處
for ...
if (A): break
....
if (B): break
...
if (C): break
else:
print "For loop break"
: 另外一個問題:else那行如果縮排退一格 結果會變得不同
: 而我不太懂else是針對什麼情況之下發生?
: 因為它是跟for對齊,但是通常不是都跟if放在一起嗎?
: break是中斷第二個for loop對吧?中斷後為何不執行else步驟呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 154.20.36.163
推 leondemon:感謝~ 04/24 10:20
推 leondemon:再問另外一個問題 python計算的數字有上限嗎? 04/24 11:00
推 Yshuan:關於質數 之前寫過MR演算法 搭配100內質數表 聽說是最快的 04/24 20:14
推 leondemon:用python寫嗎? 願不願意分享一下code? :) 04/24 22:50
→ leondemon:這篇講完後 對沒資訊背景的我獲益良多 :) 感恩 04/25 04:05
→ Holocaust123:L大你的3.講錯了 11/08 06:19