给定任意偶数，验证哥德巴赫猜想（python）

给定任意偶数，验证哥德巴赫猜想（python）

给定任意偶数，验证哥德巴赫猜想（python）

• 简要介绍
• • 算法优化
  • 代码

简要介绍

院长给了个作业，如题，很有意思，关于质数的各种定律我还不是很清楚，因此我打算尽我可能优化一波。
事先说明，码的时候基本上是脑子想到说明就马上写什么，所以变量基本是随便命名，可读性不高，看我说明一下算法就够了。
我给自己下了个条件，不打表，速度会慢很多，至少我觉得会比筛法慢，不过这才有挑战性。

算法优化

大致可以分为两个部分，一个是六除法，一个是整数p可以由一个小于sqrt （p）的整数和一个大于sqrt（p）的整数相乘而得

1.六素数除法
关于这个的文章很少，但真的好用，不必细究原理，知道就行。
大致内容为：所有素数分布于6的倍数左右两侧（除2、3外），但是，6的倍数两侧不一定是素数
由此，我们可以将原本要计算的n个数给缩小到n/3个，减少了不少计算量

2.一个是整数p可以由一个小于sqrt （p）的整数和一个大于sqrt（p）的整数相乘而得（不记得有没有名字了）
顾名思义，除了sqrt（p）本身外，必定符合，证明需要动点脑筋。由此，我们只需要计算sqrt（n）个数就可以判断素数。这里我并不是从1到sqrt（n）直接遍历，而是mod2后都是mod一个6整数倍左右的数，这个方法会有重复，类似于埃式筛与欧拉筛的区别，不建议这样用。

第一个素数从1开始，然后是2、3，再之后就是使用六素数除法，第二个素数为p-p mod 6 +1 可以保证其mod6后为1或5，而当mod6为0时直接-1即可。
若两数之和大于输入的偶数，则小的素数变大，大的素数变小，若小于了，则跳出，因为接下来就无意义了。
判断素数时先判断小的，因为判断得快，再此条件成立后才判断第二个素数。

代码

import time
import math
def judge(num):
 tm1 = time.time()   
 if num%2 != 0:
    print("请输入一个偶数")
 elif num == 2:
    print("i=1,j=1")             #因为后面直接从2开始，所以这边将小于2+2的直接硬编码
 elif num == 4:
    print("i=2,j=2")
 else:  
  i = 1
  c = 0
  d = 1
  e = 1
  sum = 0
  if num%6 == 0:
    j = num-1                    #如果六的倍数，则-1，因此mod后为5
    o = 1
  else:  
    j = num - num%6 + 1          #余数变为0，然后+1 余数变1
    o = 0
    
  while(ii:
        if i+j==num:             #从小的开始，如果不符合直接跳出，减少计算量
          k = 2
          si = round(math.sqrt(i))
          sj = round(math.sqrt(j))          
          while k<=si:
            if i%k==0:  
              break
            elif k%6 == 1:  
                k += 4           #同理变为6整数倍前后
            elif k%6 == 5:
                k += 2
            else:
                k += 1    
          if k >=si:      
           k = 2
           while k<=sj:
                if j%k==0: 
                   break
                elif k%6 == 1:
                     k += 4
                elif k%6 == 5:
                     k += 2
                else:
                   k += 1            
           if k>=sj:
               print("i="+str(i)+",j="+str(j))
               #sum += 1
               break
           else:
               break
          else:
           break
        elif i+j
						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5160361.html