-
Notifications
You must be signed in to change notification settings - Fork 0
/
Goldbach’s Conjecture.py
130 lines (116 loc) · 3.24 KB
/
Goldbach’s Conjecture.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
# coding: utf-8
# author: amani2001
# 哥德巴赫猜想
# 2000以下任意大于2的偶数都可以分解成两个素数之和
import math
import time
# 方法2 中 定义全局数组 以增加空间来减少时间复杂度
n_list = []
def isprime(n):
'''
判断n是否为素数
:param n:
:return:
'''
if n <= 1:
return 0;
if n == 2:
return 1;
k = int(math.sqrt(n)) + 1
for i in range(2, k):
if n % i == 0:
return 0
return 1
def get_list(n):
'''
生成长度为n的列表,用0和1分别表示该下标的数据是否为素数
:param n:
:return:
'''
global n_list
n_list = [0] * (n+1)
n_list[2] = 1
for i in range(3,n+1,2):
if isprime(i) == 1:
n_list[i] = 1
# print(n_list)
def method_1(n):
start_time = time.time()
for i in range(4, n+1, 2):
for j in range(2, i):
if isprime(j) == 1:
if isprime(i-j) == 1:
# print("{}={}+{}".format(i, j, i-j))
break;
if i==j:
print("error")
print("method1_time:{}".format(time.time() - start_time))
def method_2(n):
'''
直接读取列表中对应的数据是否为素数
:param n:
:return:
'''
global n_list
start_time = time.time()
# 初始化列表
get_list(n)
for i in range(4, n+1, 2):
for j in range(2, i):
if n_list[j] == 1:
if n_list[i - j] == 1:
# print("{}={}+{}".format(i, j, i - j))
break;
if i == j:
print("error")
print("method2_time:{}".format(time.time() - start_time))
def method_3(n):
# 构造n以内的所有素数列表
start_time = time.time()
prime_list = [2]
for i in range(3,n+1,2):
if isprime(i):
prime_list.append(i)
for i in range(4, n+1, 2):
for j in range(2, i):
if j in prime_list:
if i - j in prime_list:
# print("{}={}+{}".format(i, j, i - j))
break
if i == j:
print("error")
print("method3_time:{}".format(time.time() - start_time))
def method_4(n):
'''
与方法3相似,先构造n以下所有素数列表,遍历素数表中的数据,两两相加,若结果在待验证数据列表中,则输出,
设置flag用于判断循环是否所有偶数都得到了验证
:param n:
:return:
'''
# 构造n以内的所有素数列表
start_time = time.time()
prime_list = [2]
for i in range(3,n+1,2):
if isprime(i):
prime_list.append(i)
data_list = [i for i in range(4, n+1, 2)]
flag = 0
while True:
if len(data_list) != 0:
for i in prime_list:
for j in prime_list:
if i + j in data_list:
# print("{}={}+{}".format(i+j, i, j))
data_list.remove(i + j)
break
else:
flag = 1
break
if flag == 0:
print("error")
print("method4_time:{}".format(time.time() - start_time))
if __name__ == '__main__':
method_1(2000)
method_2(2000)
method_3(2000)
method_4(2000)