题目描述: 把一个偶数拆成两个不同素数的和,有几种拆法呢?现在来考虑考虑这个问题,给你一个不超过10000的正的偶数n,计算将该数拆成两个不同的素数之和的方法数,并输出。如n=10,可以拆成3+7,只有这一种方法,因此输出1.
示例:
输入:n = 4 输出:0
分析: 我们先找到10000以内的所有素数,然后再去依次 的判断是否有两个质数相加一个等于 n。 然后我们再数一下可以组合成的个数。
所以我们第一步就是找到所有的质数,如何找呢,网上有很多的办法,可以找一下 素数筛, 这方面的资料还是很多的,可以找一下。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
prime_lst = [i for i in range(2, 10000)]
prime_flag = {k:1 for k in range(0, 10000)}
prime_flag[0] = prime_flag[1] = 0
p_lst = []
for item in prime_lst:
if prime_flag[item] == 0:
continue
p_lst.append(item)
for i in range(2, 10000):
if i * item > 10000:
break
prime_flag[i*item] = 0
res = 0
for prime in p_lst:
if prime >= n//2:
break
if n-prime in p_lst:
res += 1
print(res)