AcWing 1292. 哥德巴赫猜想
原题链接
简单
作者:
皓首不倦
,
2020-09-06 11:39:32
,
所有人可见
,
阅读 375
'''
先用线性筛法将1000000以内的质数全部找出来
然后对于每一个n, 枚举比其小的质数即可
'''
# 筛选出1-N中的质数
def get_prime(N):
prime_vals = []
flag = [True] * (N+1)
for val in range(2, N+1):
if flag[val]:
prime_vals.append(val)
for p_val in prime_vals:
if val * p_val > N:
break
flag[val * p_val] = False
if val % p_val == 0:
break
return prime_vals, flag
primes, flags = get_prime(1000000)
while True:
n = int(input())
if n == 0:
break
for val in primes:
if flags[n - val]:
print('{} = {} + {}'.format(n, val, n-val))
break