真·筛法求素数

SixPy

不用加减乘除运算，筛选出素数。

1. import re
   
2. 
   
3. def primes(n):
   
4.     r=re.compile(r"^(0{2,})?(\1)+$")
   
5.     return filter(lambda x: not r.match(''.zfill(x)), range(2, n))
   
6. 
   
7. print(tuple(primes(100)))
   
8. (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)

复制代码

SixPy

简化正则表达式

1. def primes(n):
   
2.     r = re.compile(r'(0{2,})\1+')
   
3.     return filter(lambda x: not r.fullmatch(''.zfill(x)), range(2, n))

复制代码

～风介～

1. 正则大法好！
2. 头像这么漂亮，一看就是男孩子。

jerryxjr1220

在正则表达式匹配0的对数的时候其实也是用的除法，不过这个方法挺新颖的！

jerryxjr1220

不过有一点不是很明白 re.complie(r'^(0{2,})\1+$') 为什么是用+而不是用{2,} 质数应该也能匹配一次的呀，2次以上匹配不了才对啊？

SixPy

jerryxjr1220 发表于 2016-12-11 09:46
不过有一点不是很明白 re.complie(r'^(0{2,})\1+$') 为什么是用+而不是用{2,} 质数应该也能匹配一次的呀，2 ...

(0{2,})\1+

(0{2,}) 代表一个组合
\1  代表 和前一个相同的组合
这样，已经是2个组合了
+ 表示有1个以上相同的组合

jerryxjr1220

SixPy 发表于 2016-12-11 10:12
(0{2,})\1+

(0{2,}) 代表一个组合

哦，这样，明白了

jerryxjr1220

不过发现用这个筛选法有个缺陷，就是对于稍微大一点质数（比如5000或者10000以上），就基本上算不出来了，毕竟是通过字符串匹配的方式。
测试了3000以下的情况：

1. import re
   
2. import time
   
3. def primes(n):
   
4.     r=re.compile(r"^(0{2,})?(\1)+$")
   
5.     return filter(lambda x: not r.match(''.zfill(x)), range(2, n))
   
6. 
   
7. start = time.time()
   
8. p = list(primes(3000))
   
9. end = time.time()
   
10. print ("Time used: %.3f sec" % (end-start))

复制代码

输出：
Time used: 4.618 sec

SixPy

jerryxjr1220 发表于 2016-12-11 11:45
不过发现用这个筛选法有个缺陷，就是对于稍微大一点质数（比如5000或者10000以上），就基本上算不出来了， ...

求大素数本身就是个难题，
分解大素数之难度，是作为RSA非对称加密的基石。

本贴1楼已说明，是在不用加减乘除运算的情况下求素数。