作者APM99 ()
看板Python
标题Re: [问题] 质数_巢状回圈_菲丝恩
时间Thu Aug 10 12:50:28 2017
: 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://webptt.com/cn.aspx?n=bbs/Python/M.1502340632.A.C6F.html
1F：→ APM99: py3用四舍五入法得要 round(i/j + 0.0000000000001) 才行 08/10 12:52
2F：推 CaptainH: 你是不是误会了什麽 要判断29是不是被7整除 只要他妈的 08/10 12:59
3F：→ CaptainH: 除一下就好 08/10 12:59
4F：推 CaptainH: 四舍入+0.5好就 加一个0.000...1不知道搞什麽鬼 08/10 13:03
5F：→ CaptainH: 或者用ceil/floor 根本没这问题 08/10 13:04
6F：→ bruce0209: 要判断29是不是被7整除 我也思考了很久在说啥… 08/10 13:12
7F：→ Django: ????????? 08/10 15:47
8F：推 nknuukyo: 谢谢~ 08/10 16:00
9F：→ nknuukyo: wiki里有一段python3.6的引码，不晓得是否方便说明对应 08/10 16:04
10F：→ nknuukyo: 到原程式的关系^^" 08/10 16:04
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)
11F：→ bruce0209: 楼上是说sieve of Eratosthenes的wiki吗? 08/10 16:20
12F：→ bruce0209: 如果是的话 wiki里面那个是用删除法的 和这边不太一样 08/10 16:21
13F：→ bruce0209: 你可以看他wiki里面附的jpg应该就知道他在做什麽了 08/10 16:22
14F：→ bruce0209: 是说...有程式码了怎麽不自己trace看看 08/10 16:23
※ 编辑: APM99 (36.239.101.200), 08/10/2017 17:19:44
15F：→ stucode: ... 先不论原本的lemma是什麽 你的code真的是问题满载 08/10 19:34
16F：→ bruce0209: postive?????? 豆页女子痛... 08/10 19:37
17F：→ bruce0209: 推荐可以看一下clear code相关书....... 08/10 19:37
18F：→ stucode: isprime就return n 那while isprime:是? 08/10 19:44
19F：→ stucode: 每次call一开始j都是1 那n/j是在表现什麽? 08/10 19:45
20F：推 CaptainH: 愈写愈错XDD 平铺直叙的算法也能写这麽丑XDD 08/10 20:43