Re: [問題] 質數_巢狀迴圈_菲絲恩
: 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
08/10 12:52, 1F
推
08/10 12:59, , 2F
08/10 12:59, 2F
→
08/10 12:59, , 3F
08/10 12:59, 3F
推
08/10 13:03, , 4F
08/10 13:03, 4F
→
08/10 13:04, , 5F
08/10 13:04, 5F
→
08/10 13:12, , 6F
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
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
08/10 16:20, 11F
→
08/10 16:21, , 12F
08/10 16:21, 12F
→
08/10 16:22, , 13F
08/10 16:22, 13F
→
08/10 16:23, , 14F
08/10 16:23, 14F
※ 編輯: APM99 (36.239.101.200), 08/10/2017 17:19:44
→
08/10 19:34, , 15F
08/10 19:34, 15F
→
08/10 19:37, , 16F
08/10 19:37, 16F
→
08/10 19:37, , 17F
08/10 19:37, 17F
→
08/10 19:44, , 18F
08/10 19:44, 18F
→
08/10 19:45, , 19F
08/10 19:45, 19F
推
08/10 20:43, , 20F
08/10 20:43, 20F
討論串 (同標題文章)