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

[APM99 ()]

: 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
→ APM99: py3用四捨五入法得要 round(i/j + 0.0000000000001) 才行
推 CaptainH: 你是不是誤會了什麼 要判斷29是不是被7整除 只要他媽的
→ CaptainH: 除一下就好
推 CaptainH: 四捨入+0.5好就  加一個0.000...1不知道搞什麼鬼
→ CaptainH: 或者用ceil/floor 根本沒這問題
→ bruce0209: 要判斷29是不是被7整除 我也思考了很久在說啥…
→ Django: ?????????
推 nknuukyo: 謝謝~
→ nknuukyo: wiki裡有一段python3.6的引碼，不曉得是否方便說明對應
→ nknuukyo: 到原程式的關係^^"
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)

→ bruce0209: 樓上是說sieve of Eratosthenes的wiki嗎?
→ bruce0209: 如果是的話 wiki裡面那個是用刪除法的 和這邊不太一樣
→ bruce0209: 你可以看他wiki裡面附的jpg應該就知道他在做什麼了
→ bruce0209: 是說...有程式碼了怎麼不自己trace看看
※ 編輯: APM99 (36.239.101.200), 08/10/2017 17:19:44
→ stucode: ... 先不論原本的lemma是什麼 你的code真的是問題滿載
→ bruce0209: postive?????? 豆頁女子痛...
→ bruce0209: 推薦可以看一下clear code相關書.......
→ stucode: isprime就return n  那while isprime:是?
→ stucode: 每次call一開始j都是1 那n/j是在表現什麼?
推 CaptainH: 愈寫愈錯XDD 平鋪直敘的算法也能寫這麼醜XDD