作者WingedDragon (黃金會死鳥-死後無法復活)
看板Python
標題[問題] 質數列表
時間Thu Jun 9 15:56:53 2016
下面程式是用來產生質數表
我大概知道是用 埃拉托斯特尼篩法
不過有些部分看不懂
--
from time import time
t1 = time()
def primes(n):
p = [true] * (n/2)
for i in xrange(3, int(n**0.5)+1, 2):
if p[i/2]:
p[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
return [2] + [2*i+1 for i in xrange(1, n/2) if p[i]]
print len( primes(10**7) )
print time()-t1
--
我的問題主要有以下:
1. i/2 在奇數應該會變成浮點數, 為何 p[i/2] 不會錯誤
2. 黃色部分看不懂
來源:
http://tieba.baidu.com/p/1746377541 9樓回答
--
歷代主角： 武藤
遊戲---神抽
遊城十代---強運 不動
遊星---印卡 九十九
遊馬---搓牌
翼神龍 效果：
此卡不可特殊召喚...
神獸王 表示：同樣三祭品 我免費炸半場外加三千打點
裁龍 表示：同樣支一千 我能炸全場還不用扣血加攻
巨神兵 表示：聽說我可以特召
天空龍 表示：我現在可以捏死原作狂特召的你
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1465459017.A.285.html
※ 編輯: WingedDragon (140.112.25.105), 06/09/2016 15:57:53
1F：→ bigpigbigpig: i/2 在 Python 2 中是整數除法，5/2 = 2 而非 2.5 06/09 16:23
2F：→ bigpigbigpig: p與xrange的對映關係研究一下，黃色那行就是在實作 06/09 16:48
3F：→ bigpigbigpig: Sieve of Eratosthenes，把 i 的倍數全部刪除 06/09 16:49
我主要是語法看不懂, python 3 剛接觸, 很多語法和類 C 語言不同
p[i*i/2::i] 這句完全不知道是什麼意思
[False] * ((n-i*i-1)/(2*i)+1)
我只知道是要做出 ((n-i*i-1)/(2*i)+1) 數量的 False
我知道 埃式篩 的操作過程
不過語法看不懂, 所以黃色那句才完全看不懂
※ 編輯: WingedDragon (140.112.25.105), 06/11/2016 20:14:38
4F：→ bigpigbigpig: p[i*i/2::i]→從i*i/2到結尾，每隔i個間隔取值，即 06/11 23:55
5F：→ bigpigbigpig: index為i*i/2(=a),a+i,a+2*i,...,直到p的結尾， 06/11 23:56
6F：→ bigpigbigpig: 個人覺得這樣的最佳化有點過頭，找序列的slice算子 06/11 23:58
那 [False] * ((n-i*i-1)/(2*i)+1) 是如何和那些數字對應 ?
是一個 i 就產生一次, 還是每一個間隔產生一次 ?
※ 編輯: WingedDragon (140.112.4.192), 06/12/2016 21:10:16
7F：→ zerof: [False] 會把篩出來的位置都換成 False, 要下一次篩到 True 06/15 02:22
8F：→ zerof: 才會再執行 [False] * ____ 06/15 02:23