1+2
哥德巴赫猜想
词条下有一句：
1966年陈景润证明了“1+2”成立，即“任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个半素数的和”。
用例
测试前九十万的偶数，看他们是不是可以表示成两个素数的和。在整十万的时候进行显示打印。数量比较大会用到多进程。
素数的判断
def isp(n):
'''
the prime's check
'''
if 1 >= n:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if 0 == n % i:
return False
return True
单进程
def Goldbach(t):
'''t is [100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000]
'''
s, e = t - 100000 + 4, t + 2 #start, end
#Even numbers greater than 2 can be divided into two prime numbers, and the minimum is 4
for i in range(s, e, 2):
ist = False
for j in range(i//2 + 1):#在i的前半部分，从小的质数开始试
if isp(j):
k = i - j
if isp(k):
ist = True
if 0 == i%100000:
print("%d = %d + %d"%(i, j, k))#can't print in multiprocessing Pool
return (i, j, k)
break
if not ist:
print("Goldbach Conjecture failed")
break
每个数试前半部分就行了，从小的质数开始试，如果没有就是猜想失败或要用半素数。
分段测试
十万一段，分成[100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000]九段。
调试
>>> Goldbach(900000)
900000 = 19 + 899981
(900000, 19, 899981)
>>> Goldbach(800000)
800000 = 7 + 799993
(800000, 7, 799993)
>>>
19和899981都是素数，7和799993也都是素数。
多进程
from multiprocessing.pool import Pool
import time
import math
t = time.time()
c = 4
p = Pool(c)
seplist = [100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000]
result = p.map(Goldbach, seplist)
print(result)
p.close()
p.join()
print("multi processing time cost:" + "%d" %(time.time() - t))
time2 = time.time()
for a in seplist: Goldbach(a)
print("single processing time cost:" + "%d" %(time.time() - time2))
进程池设为4，映射map里用的函数是单进程的Goldbach。
对比
[(100000, 11, 99989), (200000, 67, 199933), (300000, 7, 299993), (400000, 11, 399989), (500000, 31, 499969), (600000, 7, 599993), (700000, 47, 699953), (800000, 7, 799993), (900000, 19, 899981)]
multi processing time cost:8
100000 = 11 + 99989
200000 = 67 + 199933
300000 = 7 + 299993
400000 = 11 + 399989
500000 = 31 + 499969
600000 = 7 + 599993
700000 = 47 + 699953
800000 = 7 + 799993
900000 = 19 + 899981
single processing time cost:28
从输出结果看进程池的方法少用了二十秒。
注意点
多进程调用Goldbach的时候，print(“%d = %d + %d”%(i, j, k))这行打印没有打印出来。只好把它们作为返回值打印出来。
扩展
打印五万的倍数，测试一千万的偶数看看。用了927秒。
single processing time cost:927
========================== RESTART: E:\python\歌德巴赫.py ==========================
50000 = 7 + 49993
100000 = 11 + 99989
150000 = 7 + 149993
200000 = 67 + 199933
250000 = 11 + 249989
300000 = 7 + 299993
350000 = 19 + 349981
400000 = 11 + 399989
450000 = 11 + 449989
500000 = 31 + 499969
550000 = 23 + 549977
600000 = 7 + 599993
650000 = 19 + 649981
700000 = 47 + 699953
750000 = 7 + 749993
800000 = 7 + 799993
850000 = 3 + 849997
900000 = 19 + 899981
950000 = 3 + 949997
1000000 = 17 + 999983
1050000 = 23 + 1049977
1100000 = 3 + 1099997
1150000 = 11 + 1149989
1200000 = 7 + 1199993
1250000 = 61 + 1249939
1300000 = 11 + 1299989
1350000 = 7 + 1349993
1400000 = 37 + 1399963
1450000 = 17 + 1449983
1500000 = 23 + 1499977
1550000 = 3 + 1549997
1600000 = 23 + 1599977
1650000 = 7 + 1649993
1700000 = 7 + 1699993
1750000 = 41 + 1749959
1800000 = 17 + 1799983
1850000 = 67 + 1849933
1900000 = 17 + 1899983
1950000 = 53 + 1949947
2000000 = 7 + 1999993
2050000 = 23 + 2049977
2100000 = 37 + 2099963
2150000 = 7 + 2149993
2200000 = 29 + 2199971
2250000 = 13 + 2249987
2300000 = 37 + 2299963
2350000 = 41 + 2349959
2400000 = 7 + 2399993
2450000 = 13 + 2449987
2500000 = 3 + 2499997
2550000 = 7 + 2549993
2600000 = 19 + 2599981
2650000 = 11 + 2649989
2700000 = 11 + 2699989
2750000 = 79 + 2749921
2800000 = 11 + 2799989
2850000 = 11 + 2849989
2900000 = 3 + 2899997
2950000 = 47 + 2949953
3000000 = 43 + 2999957
3050000 = 7 + 3049993
3100000 = 3 + 3099997
3150000 = 17 + 3149983
3200000 = 3 + 3199997
3250000 = 3 + 3249997
3300000 = 31 + 3299969
3350000 = 61 + 3349939
3400000 = 3 + 3399997
3450000 = 11 + 3449989
3500000 = 79 + 3499921
3550000 = 17 + 3549983
3600000 = 31 + 3599969
3650000 = 7 + 3649993
3700000 = 53 + 3699947
3750000 = 29 + 3749971
3800000 = 73 + 3799927
3850000 = 3 + 3849997
3900000 = 11 + 3899989
3950000 = 31 + 3949969
4000000 = 29 + 3999971
4050000 = 11 + 4049989
4100000 = 19 + 4099981
4150000 = 3 + 4149997
4200000 = 11 + 4199989
4250000 = 19 + 4249981
4300000 = 41 + 4299959
4350000 = 13 + 4349987
4400000 = 13 + 4399987
4450000 = 3 + 4449997
4500000 = 31 + 4499969
4550000 = 43 + 4549957
4600000 = 11 + 4599989
4650000 = 29 + 4649971
4700000 = 3 + 4699997
4750000 = 11 + 4749989
4800000 = 13 + 4799987
4850000 = 139 + 4849861
4900000 = 3 + 4899997
4950000 = 17 + 4949983
5000000 = 37 + 4999963
5050000 = 3 + 5049997
5100000 = 7 + 5099993
5150000 = 13 + 5149987
5200000 = 17 + 5199983
5250000 = 11 + 5249989
5300000 = 3 + 5299997
5350000 = 3 + 5349997
5400000 = 7 + 5399993
5450000 = 13 + 5449987
5500000 = 29 + 5499971
5550000 = 7 + 5549993
5600000 = 19 + 5599981
5650000 = 3 + 5649997
5700000 = 11 + 5699989
5750000 = 7 + 5749993
5800000 = 23 + 5799977
5850000 = 7 + 5849993
5900000 = 3 + 5899997
5950000 = 29 + 5949971
6000000 = 7 + 5999993
6050000 = 3 + 6049997
6100000 = 17 + 6099983
6150000 = 13 + 6149987
6200000 = 13 + 6199987
6250000 = 11 + 6249989
6300000 = 13 + 6299987
6350000 = 3 + 6349997
6400000 = 29 + 6399971
6450000 = 79 + 6449921
6500000 = 61 + 6499939
6550000 = 239 + 6549761
6600000 = 13 + 6599987
6650000 = 109 + 6649891
6700000 = 23 + 6699977
6750000 = 11 + 6749989
6800000 = 7 + 6799993
6850000 = 29 + 6849971
6900000 = 11 + 6899989
6950000 = 7 + 6949993
7000000 = 3 + 6999997
7050000 = 7 + 7049993
7100000 = 31 + 7099969
7150000 = 17 + 7149983
7200000 = 43 + 7199957
7250000 = 3 + 7249997
7300000 = 41 + 7299959
7350000 = 11 + 7349989
7400000 = 7 + 7399993
7450000 = 29 + 7449971
7500000 = 19 + 7499981
7550000 = 13 + 7549987
7600000 = 11 + 7599989
7650000 = 23 + 7649977
7700000 = 19 + 7699981
7750000 = 3 + 7749997
7800000 = 29 + 7799971
7850000 = 163 + 7849837
7900000 = 11 + 7899989
7950000 = 67 + 7949933
8000000 = 7 + 7999993
8050000 = 3 + 8049997
8100000 = 17 + 8099983
8150000 = 73 + 8149927
8200000 = 59 + 8199941
8250000 = 7 + 8249993
8300000 = 19 + 8299981
8350000 = 3 + 8349997
8400000 = 13 + 8399987
8450000 = 43 + 8449957
8500000 = 23 + 8499977
8550000 = 31 + 8549969
8600000 = 7 + 8599993
8650000 = 71 + 8649929
8700000 = 7 + 8699993
8750000 = 19 + 8749981
8800000 = 3 + 8799997
8850000 = 13 + 8849987
8900000 = 3 + 8899997
8950000 = 41 + 8949959
9000000 = 7 + 8999993
9050000 = 13 + 9049987
9100000 = 11 + 9099989
9150000 = 19 + 9149981
9200000 = 3 + 9199997
9250000 = 17 + 9249983
9300000 = 23 + 9299977
9350000 = 3 + 9349997
9400000 = 11 + 9399989
9450000 = 11 + 9449989
9500000 = 67 + 9499933
9550000 = 17 + 9549983
9600000 = 23 + 9599977
9650000 = 13 + 9649987
9700000 = 41 + 9699959
9750000 = 11 + 9749989
9800000 = 3 + 9799997
9850000 = 11 + 9849989
9900000 = 7 + 9899993
9950000 = 37 + 9949963
10000000 = 29 + 9999971
半素数
若一个自然数可以表示成两个素数乘积的形式，这个自然数就叫作半素数（又名半质数、二次殆素数）。最小的47个半素数是：
4，6，9，10，14，15，21，22，25，26，33，34，35，38，39，46，49，51，55，57，58，62，65，69，74，77，82，85，86，87，91，93，94，95，106，111，115，118，119，121，122，123，129，133，134，141，142.
这些数共有3或4个因数（包括自身）。半素数一定是合数，但合数不一定是半素数。
缅怀数学家
一千万对他们来说还是很小的数，测试没有碰到半素数。
 1986年，陈景润在研究数论问题 |
|---|