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

作者: nknuukyo (我無所能因敵成體)   2017-08-09 14:28:15
各位前輩好,
最近在看python的一些入門書,第二本我是選《菲絲恩教你學會python》,
覺得他們編的不錯,但有些小bug不確定是自已還是書本的問題,想請各位前輩幫忙指點

過去很少用巢狀寫質數,本來以為bug在縮排,但沒檢查到。
程式碼如下:
===
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))
===
輸出為:
2 is prime
3 is prime
7 is prime
11 is prime
13 is prime
17 is prime
19 is prime
23 is prime
29 is prime
31 is prime
37 is prime
41 is prime
43 is prime
47 is prime
53 is prime
59 is prime
61 is prime
67 is prime
71 is prime
73 is prime
79 is prime
83 is prime
89 is prime
97 is prime
===
我試著在程式碼裡面加一些內容,呈現i跟j的狀態,
但都不會跑出5是質數,會說i=5時,非質數,j=2。
不是很搞得清楚bug在哪裡,還請前輩們慧眼點明~
作者: nknuukyo (我無所能因敵成體)   2017-08-09 14:29:00
使用版本為3.6.1
作者: tsoahans (ㄎㄎ)   2017-08-09 15:32:00
int(i/j)+1改int(i/j)+2
作者: CaptainH (Cannon)   2017-08-09 16:58:00
i/j 這是錯的
作者: stucode   2017-08-09 19:06:00
這問題網站上就有勘誤資訊 不過我也不懂i/j那邊的邏輯
作者: bruce0209 (士賢)   2017-08-09 20:35:00
for j 的前一行加上print("i:"+str(i)+" j:2~"+str(int(i/j)+1))if j>i**0.5的前一行加上print(str(j)+" > "+str(i**0.5)+" ? ")應該就不會找不到BUG了吧...話說我也不懂i/j的原因 求解
作者: mikapauli (桜花)   2017-08-09 20:51:00
最小就近似根號i,隨便給個上限而已吧。想法很奇怪就是
作者: uranusjr (←這人是超級笨蛋)   2017-08-09 23:06:00
我問一句這是完全照書上打的嗎, 如果是的話感覺不算好書看了勘誤感覺應該是照書上沒錯, 這種爛 code 也出書...i/j 寫成 int(i**0.5) 應該就看得懂了吧, 這兩個等價把的最後一個 iteration j = (i/j-1)+1 移項應該就懂了
作者: bruce0209 (士賢)   2017-08-09 23:25:00
懂原義了不過還是很詭異...j^2=(i**0.5)^2然後移項的意思吧....可是 j1 = (i/j2-1)+1 在運作上j1和j2不相等吧...
作者: TitanEric (泰坦)   2017-08-10 00:19:00
我覺得程式邏輯很奇怪…
作者: uranusjr (←這人是超級笨蛋)   2017-08-10 00:49:00
是啊, 因為 range 的參數是在初始化時就決定, 所以裡面的 j 會是「前一個 i iteration」的 j 的最後一個值會覺得詭異奇怪是正常的, 因為寫出這樣的東西要嘛根本寫錯要嘛腦袋打結異於常人, 無論是哪種在一般公司都會被電到翻, 別說寫書出來賣錢了...
作者: bibo9901 (function(){})()   2017-08-10 08:31:00
因為i是偶數時, j只會跑到2. 所以下一個i(奇數)時, 就會使j介於2~i/2, 這個上限大於sqrt(i), 所以大部份是對的
作者: APM99 (血統純正台北人)   2017-08-10 08:50:00
這篇寫法是很標準的求質數方法阿 不詭異吧改成這樣即可 : http://imgur.com/Z2axM0O非常標準的作法 ~~只是2會被忽略掉 沒啥差#忘了說 這篇一開始的寫法5沒印出來是被誤差害死的...盡量避免掉會有誤差的寫法
作者: stucode   2017-08-10 10:15:00
看了眾位板友解說豁然開朗 原來是i/j是從j>sqrt(i)來的
作者: APM99 (血統純正台北人)   2017-08-10 10:17:00
我中午在發篇文解釋一下 這篇方法是高中學的A*B=P求質數法
作者: nknuukyo (我無所能因敵成體)   2017-08-10 10:18:00
感謝APM99大~ !!
作者: stucode   2017-08-10 10:19:00
不過原書code真的寫得很不好 勘誤版本雖然結果正確建議原PO看過就好
作者: APM99 (血統純正台北人)   2017-08-10 10:31:00
我的寫法是錯的! 我沒避免掉誤差可惜我現在沒法發文

Links booklink

Contact Us: admin [ a t ] ucptt.com