哥德巴赫猜想在Python中验证最多N个

问题描述 投票：0回答：3

我似乎在我的 python 代码中创建了一个无限循环。我的目标是创建一个函数“检查”，它使用我之前的“哥德巴赫”函数来确认每个大于 4 的偶数以及输入的 N 符合哥德巴赫猜想（我知道这是一个毫无意义的过程，但它是为了我的任务）。我知道我的“哥德巴赫”函数运行良好，并生成一对素数，对于“好”输入，总和为 N，对于“坏”输入，总和为 (0,0)。我希望我的检查函数对于所有大于 4 的偶数输入返回 True（因为这些符合猜想），对于任何奇数输入返回 False。但是，当我在控制台中尝试检查功能时，我的代码将无法运行，因此出现了问题 - 你知道它是什么吗？

def goldbach(N):
    x, y = 0, 0
    result = 0
    if N % 2 == 0:
        prime = odd_primes(N)
        while result != N:
            for i in range(len(prime)):
                if result == N: break
                x = prime[i]
                for j in range(len(prime)):
                    y = prime[j]
                    result = x + y
                    if result == N: break 
    return x, y 

def check(N):
    for n in range(4, N+1):
        if n % 2 ==0:
            g = goldbach(n)
            if g == (0,0):
                return False
            else:
                return True
python
3个回答
1
投票

您在检查范围中的第一项后立即返回。遇到不符合预期的项目需要立即返回

False
，如果全部符合预期则最后返回
True
。

如果您只想查看偶数，请在 

2
函数中使用 
range()
的步长，而不是测试每个数字来查看它是偶数还是奇数。

def check(N):
    for n in range(4, N+1, 2):
        if goldbach(n) == (0, 0):
            return False
    return True

您不需要 

while
中的 
goldbach()
循环。两个 
for
循环测试素数的所有组合。如果他们找不到匹配的对，就没有理由重新启动他们。

您还可以简化和优化循环。内部循环只需要测试从 

x
开始的素数，因为 
y < x
的素数对已经在 
x
的早期迭代中进行了测试。

def goldbach(N):
    if N % 2 == 0:
        prime = odd_primes(N)
        for i, x in enumerate(prime):
            for y in prime[i:]:
                if x + y == N:
                    return x, y 
    return 0, 0

但是，我认为您的代码应该仍然有效，这表明问题实际上是 

odd_primes()
没有返回 
N
之前的所有素数。

0
投票

我刚刚为你的函数创建了一个替代品

odd_primes(N)
，返回所有小于或等于N的素数的列表（那里有2似乎没有什么区别）。您的 
check()
函数似乎会检查 4 到 N 之间的所有整数（包括 4 和 N），如果找到未找到哥德巴赫和的内容，则返回 
False
。然而，正如其他人指出的那样，一旦找到一对，它也会立即返回 
True
。所以当你运行 
check()
时会发生什么，从数字 4 开始，发现它的哥德巴赫对是 (2,2)，然后立即通过返回 
True
退出函数，忽略 4 和 N 之间的任何其他值。

当我用 

return True
语句替换 
print
并在整个循环后添加 `return True 时：

def check(N):
    for n in range(4, N+1):
        if n % 2 ==0:
            g = goldbach(n)
            if g == (0,0):
                print("No sum found for %d !" % n)
                return False
            else:
                print("%d is equal to %d + %d" % (n, g[0], g[1]))
    return True

然后运行 

check(20)
例如，我得到：

4 is equal to 2 + 2
6 is equal to 3 + 3
8 is equal to 3 + 5
10 is equal to 3 + 7
12 is equal to 5 + 7
14 is equal to 3 + 11
16 is equal to 3 + 13
18 is equal to 5 + 13
20 is equal to 3 + 17

顺便说一句，如果你只想知道给定的偶数是否可以写成两个素数之和，但你不关心实际的素数对是什么，你可以这样做：

def goldbach(N):
    if N % 2 == 0:
        primes = odd_primes(N)
        # Generate a list of all the i+j sums where j >= i (skipping
        # most duplicates this way), and see if N is among the sums.
        sums = [i + j for i in primes for j in primes[primes.index(i):]]
        return(N in sums)
    else:
        print("N must be even.")
        return(False)
0
投票

我不会建立一个素数表。这对于少数人来说效果很好。我对素数使用了简单的 6k±1 测试。

# Goldbach's Conjecture tester for all even numbers up to N. 
import sys
#from gmpy2 import is_prime
# or use home grown IsPrime
sys.set_int_max_str_digits(20000)

def IsPrime(n):  
    if (n <= 1):  
        return False      
    if (n <= 3):  
        return True        
    if (n%2 == 0 or n%3 == 0):  
        return False      
    for i in range(5,int(n**.5)+1): 
        if (n%i == 0 or n%(i+2) == 0):  
            return False          
    return True  

def goldbach(number):    
    if number == 4:
        #print("\n2 + 2 = 4\n")
        return 2,2
    elif IsPrime(number - 3 ):
        #print(f"\n3 + {number-3:,} = {number}\n")
        return 3,number-3
    else:
        for p in range(5, number, 6): # just 6k±1 
            if IsPrime(p ) and IsPrime(number-p ): 
                #print(f"\n{p:,} + {number-p:,} = {number:,}\n")
                return p,number-p
            elif IsPrime(p+2) and IsPrime(number-(p+2) ):
                #print(f"\n{p+2:,} + {number-(p+2):,} = {number:,}\n")
                return p+2,number-p+2
        return 0,0

def check(N):
    for n in range(4,N+1,2):
        g = goldbach(n)
        if g == (0,0):
            print("No sum found for %d !" % n)
            raise Exception(f"Found a counter-example to the Goldbach conjecture: {n}")
        else:
            print("%d is equal to %d + %d" % (n, g[0], g[1]))
    return True

if __name__=="__main__":
    N = 0
    args = len(sys.argv)
    if args > 1:
        N = int(sys.argv[1])
    print("This is a test of Goldbach's Conjecture that for all even integers")
    print("greater than 2 there are two primes that add up to that even number.\n")
    
    while (N < 3):
        N = int(input("Please enter a number > 3 to check all evens to N> "))
    print("All even numbers up to %d will be tested" % N) 
    check(N)

输出：

$ python goldbach_range.py 
This is a test of Goldbach's Conjecture that for all even integers
greater than 2 there are two primes that add up to that even number.

Please enter a number > 3 to check all evens to N> 65
All even numbers up to 65 will be tested
4 is equal to 2 + 2
6 is equal to 3 + 3
8 is equal to 3 + 5
10 is equal to 3 + 7
12 is equal to 5 + 7
14 is equal to 3 + 11
16 is equal to 3 + 13
18 is equal to 5 + 13
20 is equal to 3 + 17
22 is equal to 3 + 19
24 is equal to 5 + 19
26 is equal to 3 + 23
28 is equal to 5 + 23
30 is equal to 7 + 27
32 is equal to 3 + 29
34 is equal to 3 + 31
36 is equal to 5 + 31
38 is equal to 7 + 35
40 is equal to 3 + 37
42 is equal to 5 + 37
44 is equal to 3 + 41
46 is equal to 3 + 43
48 is equal to 5 + 43
50 is equal to 3 + 47
52 is equal to 5 + 47
54 is equal to 7 + 51
56 is equal to 3 + 53
58 is equal to 5 + 53
60 is equal to 7 + 57
62 is equal to 3 + 59
64 is equal to 3 + 61
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.