验证“哥德巴赫猜想”

最后的魁拔

那位老哥看看哪里有错误,测试不完全通过，还超时，希望大佬能优化一下

数学领域著名的“哥德巴赫猜想”的大致意思是：任何一个大于2的偶数总能表示为两个素数之和。比如：24=5+19，其中5和19都是素数。本实验的任务是设计一个程序，验证20亿以内的偶数都可以分解成两个素数之和。

输入格式：

输入在一行中给出一个(2, 2 000 000 000]范围内的偶数N。

输出格式：

在一行中按照格式“N = p + q”输出N的素数分解，其中p ≤ q均为素数。又因为这样的分解不唯一（例如24还可以分解为7+17），要求必须输出所有解中p最小的解。

输入样例：24         
输出样例：24 = 5 + 19

1. #判断素数函数
   
2. def prime(p):
   
3.     flag = 0
   
4.     if p == 2:
   
5.         return True
   
6.     else:
   
7.         for i in range(2,p):
   
8.             if p%i==0:
   
9.                 flag = 0
   
10.                 break
    
11.             else:
    
12.                 flag = 1
    
13.                
    
14.         if flag:
    
15.             return True
    
16.         else:
    
17.             return False
    
18. a = int(input())
    
19. d=[]
    
20. for i in range(1,a+1):
    
21.     if prime(i):
    
22.         d.append(i)
    
23. sum1 = 0
    
24. flag = 0
    
25. length = len(d)
    
26. for i in d:
    
27.     for j in range(i,length):
    
28.         if i+d[j]==a:
    
29.             print("{} = {} + {}".format(a,i,d[j]))
    
30.             flag = 1
    
31.             break
    
32.     if flag==1:
    
33.         break     
    

复制代码

fan1993423

哈哈，你可以叫zlzlt做成一道题了

最后的魁拔

fan1993423 发表于 2020-2-17 16:39
哈哈，你可以叫zlzlt做成一道题了

。。。

wp231957

可以判断 x  和 24-x 同时是素数即可

fan1993423

最后的魁拔 发表于 2020-2-17 16:58
。。。

20亿确实太大了，python运行不起来，我觉得20万以内还勉勉强强

Sungne_jer

优秀

Stubborn

转换下思想，具体没有实现过，题目会根据给定的N求 素数范围，而且，还是求最小的解，意味这有一个最大解。

所以只要找到一个 N`的素数（比N小的最大素数），再尝试另外一个素数的解。

建议用米勒-罗宾算法，不要用线筛，或者打表，更加别去强算。


米勒-罗宾算法可以快判2^63大小的数字

fan1993423

Stubborn 发表于 2020-2-17 22:57
转换下思想，具体没有实现过，题目会根据给定的N求 素数范围，而且，还是求最小的解，意味这有一个最大解。 ...

可以的，get一个新算法，我 马上看一下这个算法

Stubborn

fan1993423 发表于 2020-2-17 23:02
可以的，get一个新算法，我 马上看一下这个算法

实现了吗？

fan1993423

Stubborn 发表于 2020-2-18 22:45
实现了吗？

没有哦