古希腊的数论
- 目标
- 图形数
- 埃拉托斯特尼筛法
- 准备工作
- 代码
- 测试
- 埃拉托斯特尼Python
- 比较
- 代码
- Python改成2N
- 应用
- 素数的判断
- 匹配——散列法
- 扩展头尾素数
- 验证
目标
用埃拉托斯特尼筛法找201前的素数。把STL改成Python实现，对比之前的求素数算法。
 运行结果 |
|---|
图形数
毕达哥拉斯学派观察到，有些数字不能表现成矩形形状——两个边都大于一的矩形，这种数叫做素数或质数。这样就好理解了，之前一直想0，1为什么不是素数；是谁想到这样的数的，有来干什么的。其实0出现得很晚。
埃拉托斯特尼筛法
准备工作
古人早知道偶数都不是素数。所以筛前的表是从3开始的奇数。
P = [(True,(i+1)*2+1) for i in range(100)]
如图：
 筛前的表是从3开始的奇数 |
|---|
代码
def mark_sieve(first,last,factor):
P[first]=False
while(last-first>factor):
first += factor
P[first]=False
#template <RandomAccessIterator I,Integer N>
def sift(first,n):
i = 0 #N i(0)
index_square = 3 # N index_square(0)
while index_square < n:
# invariant: index_square = 2i^2 + 6i + 3
if P[first]:
mark_sieve(first+index_square,
first+n,
i+i+3)
i += 1
index_square = 2*i*(i+3)+3
测试
sift(0,100)
P
[(True, 3), (True, 5), (True, 7), False, (True, 11), (True, 13), False, (True, 17), (True, 19), False, (True, 23), False, False, (True, 29), (True, 31), False, False, (True, 37), False, (True, 41), (True, 43), False, (True, 47), False, False, (True, 53), False, False, (True, 59), (True, 61), False, False, (True, 67), False, (True, 71), (True, 73), False, False, (True, 79), False, (True, 83), False, False, (True, 89), False, False, False, (True, 97), False, (True, 101), (True, 103), False, (True, 107), (True, 109), False, (True, 113), False, False, False, False, False, False, (True, 127), False, (True, 131), False, False, (True, 137), (True, 139), False, False, False, False, (True, 149), (True, 151), False, False, (True, 157), False, False, (True, 163), False, (True, 167), False, False, (True, 173), False, False, (True, 179), (True, 181), False, False, False, False, (True, 191), (True, 193), False, (True, 197), (True, 199), False]
False是划掉的项，比如（True,9）变成了False.
埃拉托斯特尼Python
把素数的倍数全部划掉。
def eratosthene(n):
'''
>>> eratosthene(100)
[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]
'''
P=[True]*n
answ=[2]#The first is 2,skip 0 and 1
for i in range(3,n,2):#The step is 2，skip all even numbers
if P[i]:
answ.append(i)
for j in range(2*i,n,i):
P[j]=False
return answ
比较
比较一亿个数字时，python通用的写法用时更少：
test(100000000)
埃拉托斯特尼 Python 9.892973899841309
埃拉托斯特尼 STL 44.09530520439148
代码
def test(N):
import time
s = time.time()
eratosthene(N)
print("埃拉托斯特尼 Python",time.time()-s)
s = time.time()
P = [(True,(i+1)*2+1) for i in range(N)]
sift(0,N,P)
print("埃拉托斯特尼 STL",time.time()-s)
但给sift和mark_sieve都添加了一个形参P，如sift(0,N,P)。而且准备筛选前的P也不用一亿。STL里面还考虑到了第一个划掉的数是素因子的平方。
都是两层循环，STL还可以应用更多观察到的规律，应该是更快的，至少在C++里是最好的。
Python改成2N
上面STL找的是两亿里的素数，把eratosthene(N)里的N改成2*N，测试结果如下。
test(100000000)
埃拉托斯特尼 Python 21.3486430644989
埃拉托斯特尼 STL 44.855021476745605
应用
素数的判断
陈景润证明文章里使用一个数平方根以下的数，看是不是这个数的因子来判断素数。
匹配——散列法
散列函数中用到了一个十七位的大素数。
扩展头尾素数
def f(n, s):
for k in s:
if k * k > n: break
if 0 == n % k: return None
return n
s = []
for n in range(2, 100000):#生成十万以内的素数
r = f(n, s)#判断素数
if r : s.append(r)
for p in permutations([1, 3, 5, 7, 9], 5):
'''get rid of the head and tail,it also a prime number'''
if s.count(reduce(lambda x, y: 10 * x + y, p[1:-1])) and s.count(reduce(lambda x, y: 10 * x + y, p)) and 1!=p[2] and 9!=p[2]:
print(p)
print(reduce(lambda x, y: 10 * x + y, p[1:-1]))
print(reduce(lambda x, y: 10 * x + y, p))
先生成十万以内的素数，前五个奇数组成的数在十万以内。这里是用一个数是不是素数的倍数来判断它是不是素数，跟陈景润证明里用的不一样。
1和9不能做中间的数。程序求奇数[1, 3, 5, 7, 9]组成的去掉头尾还是素数的素数。输出结果如下：
(1, 3, 5, 9, 7)
359
13597
(5, 3, 7, 9, 1)
379
53791
(7, 9, 5, 3, 1)
953
79531
(9, 1, 5, 7, 3)
157
91573
(9, 5, 7, 1, 3)
571
95713
验证
用陈景润证明文章里的isp判断。
isp(359)
True
isp(13597)
True
isp(379)
True
isp(53791)
True
isp(953)
True
isp(79531)
True
isp(571)
True
isp(95713)
True
isp(9)
False