Re: [問題] 質數_巢狀迴圈_菲絲恩

看板Python作者時間8年前發表 (2017/08/10 04:50), 8年前編輯推噓4(4016)
留言20則, 6人參與, 最新討論串2/2 (看更多)
: i=j=1 : for i in range(2,100,1): : for j in range(2,int(i/j)+1): : if(not i%j): : break : if j>i**0.5: : print('%d is prime'%(i)) 這裡用的數學方法是大家高中都學過的 Sieve of Eratosthenes(wiki中文:埃拉托斯特尼篩法) 其中的一個引理 想判斷 i = 29 能不能被 7 整除 只需要判斷4項 ,即 29/2 29/3 29/4 29/5 能不能整除 驗證 29/6 已經沒意義了,因為 7*5 已經大於29了 i/j是一種等分的概念. #回到python虛擬碼 i=j=1 for i in range(2,100,1): for j in range(2,(無條件進位到整數的i/j) +1): if(not i%j): break if j>i**0.5: print('%d is prime'%(i)) # 1. 灰色 +1 是python range特性 2. 淺藍色可能只是想打出2,不然跟等分法並不連貫~, 3. 紅色部分 一般都是取巧用四捨五入法,結果python沒印出 5.. 才發現 python3 中 round(2.5) = 2 python2 中 round(2.5) = 3 可見 https://stackoverflow.com/questions/10825926/python-3-x-rounding-behavior -- 來玩躲貓貓~我當鬼,阿哈 。 。 嗚哇,你本來就是鬼啊~ > < ╯ ﹨ cAshoNly -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.239.101.200 ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1502340632.A.C6F.html

08/10 12:52, , 1F
py3用四捨五入法得要 round(i/j + 0.0000000000001) 才行
08/10 12:52, 1F

08/10 12:59, , 2F
你是不是誤會了什麼 要判斷29是不是被7整除 只要他媽的
08/10 12:59, 2F

08/10 12:59, , 3F
除一下就好
08/10 12:59, 3F

08/10 13:03, , 4F
四捨入+0.5好就 加一個0.000...1不知道搞什麼鬼
08/10 13:03, 4F

08/10 13:04, , 5F
或者用ceil/floor 根本沒這問題
08/10 13:04, 5F

08/10 13:12, , 6F
要判斷29是不是被7整除 我也思考了很久在說啥…
08/10 13:12, 6F

08/10 15:47, , 7F
?????????
08/10 15:47, 7F

08/10 16:00, , 8F
謝謝~
08/10 16:00, 8F

08/10 16:04, , 9F
wiki裡有一段python3.6的引碼,不曉得是否方便說明對應
08/10 16:04, 9F

08/10 16:04, , 10F
到原程式的關係^^"
08/10 16:04, 10F
wiki是一次做全部,而我們用的引理是去判斷一個數是不是質數 所以我們得一個一個慢慢做 類似的程式碼可以改寫如下 #python import math def postive(n): j=1 isprime = True while isprime: for j in range(2,math.ceil(n/j)):#也可以用wiki的n (我們得減1) if( n%j == 0): #wiki是移除,我們跳出 isprime=False break if (isprime): #這部分用淺藍字(較瑣碎)就能直接對應P[p]**2 >= P[-1]: return(n) #輸入 postive(29) 是質數的話會就會 返回29 ,否則不返回東西 #生出2~120的質數列表來 res =[] for ii in range(2,120): res.append(postive(ii)) L = list(filter(None, res))#移除列表中的None print(L)

08/10 16:20, , 11F
樓上是說sieve of Eratosthenes的wiki嗎?
08/10 16:20, 11F

08/10 16:21, , 12F
如果是的話 wiki裡面那個是用刪除法的 和這邊不太一樣
08/10 16:21, 12F

08/10 16:22, , 13F
你可以看他wiki裡面附的jpg應該就知道他在做什麼了
08/10 16:22, 13F

08/10 16:23, , 14F
是說...有程式碼了怎麼不自己trace看看
08/10 16:23, 14F
※ 編輯: APM99 (36.239.101.200), 08/10/2017 17:19:44

08/10 19:34, , 15F
... 先不論原本的lemma是什麼 你的code真的是問題滿載
08/10 19:34, 15F

08/10 19:37, , 16F
postive?????? 豆頁女子痛...
08/10 19:37, 16F

08/10 19:37, , 17F
推薦可以看一下clear code相關書.......
08/10 19:37, 17F

08/10 19:44, , 18F
isprime就return n 那while isprime:是?
08/10 19:44, 18F

08/10 19:45, , 19F
每次call一開始j都是1 那n/j是在表現什麼?
08/10 19:45, 19F

08/10 20:43, , 20F
愈寫愈錯XDD 平鋪直敘的算法也能寫這麼醜XDD
08/10 20:43, 20F
文章代碼(AID): #1PY-OOnl (Python)
討論串 (同標題文章)
文章代碼(AID): #1PY-OOnl (Python)