python - 求和最大路径算法给出了意想不到的解决方案

Question

在我的输入中 numbers[3][2] == 62 一切正常算法工作正常 但是 numbers[3][2] == 63 算法给了我意想不到的结果我无法理解这个原因。 我试着设计这样的算法你只能去非素数并且只能走root > leftchild or root > rightchild 一些例子:

10
20 23
40 50 60
65  60 69 80

10 +20+50+69 = 149 右一 10 +0(23) + 60+80 = 150 错了，我们不能走质数!

我已经尝试调试该算法的几乎所有部分，但我无法理解问题原因

import sys


numbers = [
       [10],
     [20, 23],
    [40, 50, 60],
  [10, 20, 63, 80]
]


def IsNotPrime(a ): # 
    sayac = 0
    if(a == 0 or a == 1 ):
        sayac = sayac +1
    else:
        for i in range(2,a):
            if(a % i == 0 ):
                sayac = sayac +1
            else:
                sayac = sayac
    if(sayac == 0):
        return False# prime
    else:
        return True # non prime

def bigger(a,b):
    if(a>b ):
        return a
    elif(b>=a ):
        return b


for i in range((len(numbers)-2),-1,-1): 
    for j in range (0,(len(numbers[i]))):
        a = numbers[i][j]#root
        b = numbers[i+1][j]#left chield
        c = numbers[i+1][j+1]#right chield
        if( IsNotPrime(a) and IsNotPrime(b) and IsNotPrime(c) ):
            numbers[i][j] = (a + bigger(b,c))

        elif(IsNotPrime(a) and IsNotPrime(b)):
               numbers[i][j] = (a + b)

        elif( IsNotPrime(a) and IsNotPrime(c) ):
               numbers[i][j] = (a + c)


print( numbers[0][0])

代码给出结果 90 但是 对于这种情况，我期望结果 143 10+20+50+63 = 143(最大和路径只能运行根到对等体，不能遍历素数)。

Answer 1

您不是在检查各个数字是否是质数。您正在检查运行总计。 50 + 63 = 113 是质数，因此该路径是不允许的。