[問題] 找前 40 個質數出現奇怪的問題

[Equalmusic (Cosmajoonitist)]

i = 0  #dummy index
x = 3  #prime candidates
p = 2  #dividers

print 2 #start from 2

while (i < 40):
    while (x > p): #get out of the loop only when p >=x
        if x%p != 0:
            p = p + 1
        else: x = x + 1
    print x
    i = i + 1
    x = x + 2
    p = 2
print 'Done!'

我是寫程式新手最近剛開始學 Python

我想計算前面 40 個質數

跑出來多半正確, 質數都沒有漏掉, 但卻多出來一些不是質數的比如 27 跟 35

但我把 27 丟回去怎麼看也不覺得會跑出 loop 之外

想請板上先進幫我看一下是怎麼回事...感激不盡 Orz....

--

ｅ^(ｉπ) ＋ １ = ０

- Leonhard Euler

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 183.11.73.179
※ 編輯: Equalmusic      來自: 183.11.73.179        (11/10 23:13)
推 autumned:看不太懂...你的排板是不是跑掉了@@
→ suzuke:排版沒有亂, 但是演算法有問題
推 cooper6334:else: x = x + 1    p也要回到2吧
→ suzuke:沒錯, p要讓他回到2, 不然會有些因數沒有檢查到
→ Equalmusic:阿原來如此！太感謝了！
推 yangcy0726:else: x = x + 1 後面要加 p = 2 讓 p 重頭檢驗
→ suzuke:題外話, 這個演算法還真的讓我困惑了一下QQ
→ Equalmusic:Python 板的前輩真熱心, 短短幾分鐘就這麼多回應 >_<b
→ Equalmusic:是喔...我的演算法很奇怪嗎？XDDD
→ suzuke:因為你每個數都要檢查2~自己本身, 所以會比較沒效率
→ suzuke:其實只要檢查2~自己本身之前的質數就好
→ suzuke:另外善用break會讓你的code看起來比較易懂
→ suzuke:甚至只要檢查到sqrt(自己本身)就可以了
→ Equalmusic:原來如此。我爬文的時候有爬到 break, 但我目前還沒學
推 autumned:0.0"""
→ Equalmusic:所以想先用有教到的指令來做就好..
→ suzuke:也是~ 慢慢來比較好, 加油:)
推 kusoayan:寫質數檢驗可以慢慢修XD 慢慢調整演算法的效率