查找素因子的函数会覆盖其部分结果

Question

我正在尝试制定一种算法来显示数字是由哪些素数因子组成的。我编写了以下代码（未优化），它将一个数字分成其组成的 2 个数字。然后我这样做，直到找到这些数字是由什么基数（质数）组成的。我有问题，我不断重置最终列表，并且我不想使用全局变量。

知道如何正确执行此操作吗？

以下代码的预期输出应该是

[2, 2, 5, 7]

，因为 4 × 35 = 140、2 × 2 = 4 和 5 × 7 = 35。

def is_prime(n:int) -> bool: 
    if n==2 or n==3: 
        return True
    for i in range(3, n//2+1): 
        if n%i==0: 
            return False
    return True

def made_of(n:int) -> list[int]: 
    v = []
    for i in range(2, n//2+1): 
        for j in range(2, n//2+1): 
            if i*j==n: 
                v += [i]
                v += [j]
                return v

def is_prime_list(v:list[int]) -> bool: 
    for i in range(0, len(v)): 
        if is_prime(v[i])!= True: 
            return False
    return True

def made_of_prime(v:list[int]) -> list[int]: 
    p = []
    w = []
    if is_prime_list(v)==False: 
        for i in range(0, len(v)): 
            if is_prime(v[i])==True:
                w += [v[i]]
            else: 
                p += made_of(v[i])
                return made_of_prime(p)
    else: 
        w += v
        return w
    return w


if __name__=="__main__": 
    print(made_of_prime(made_of(140)))

Answer 1

为了避免重置最终列表并消除对全局变量的需要，您可以使用递归方法，将当前结果作为参数传递给递归调用。 可以试试这个代码：

def is_prime(n: int) -> bool:
  if n < 2:
      return False
  if n == 2:
      return True
  if n % 2 == 0:
      return False
  for i in range(3, int(n**0.5) + 1, 2):  # Check up to the square root of n, skipping even numbers
      if n % i == 0:
          return False
  return True


def prime_factors(n: int, factors=None) -> list[int]:
  if factors is None:
      factors = []

  for i in range(2, int(n**0.5) + 1):  # Check up to the square root of n
      if n % i == 0:
          # Found a factor, recurse for both i and n // I
          prime_factors(i, factors)
          prime_factors(n // i, factors)
          return factors  # Return early after breaking into factors

  # If no factors are found, n itself is a prime
  factors.append(n)
  return factors


if __name__ == "__main__":
  num = 140
  result = prime_factors(num)
  print(f"The prime factors of {num} are: {sorted(result)}")

Answer 2

事实证明，您的代码只需进行一些小调整即可工作。 我简化了你的函数

made_of_prime()

来附加通过以下方式获得的素数 对已知素因数列表的递归调用。

由于我们只让素数进入

w

，所以我们不需要检查它。 这消除了对功能

is_prime_list()

的需求，我将其删除。 事实证明，你对自己代码结果的不信任是罪魁祸首。

此外，我冒昧地在此处应用了一些格式并进行了最小的更改 在那里。

看一下以下稍微修改过的代码版本：

def is_prime(n: int) -> bool:
    if n in [2, 3]:
        return True
    for i in range(3, n//2+1):
        if n % i == 0:
            return False
    return True


def made_of(n: int) -> list[int]:
    v = []
    for i in range(2, n//2+1):
        for j in range(2, n//2+1):
            if i * j == n:
                v += [i]
                v += [j]
                return v
    return []


def made_of_prime(v: list[int]) -> list[int]:
    w = []
    for i in v:
        if is_prime(i):
            w += [i]
        else:
            p = made_of(i)
            w += made_of_prime(p)
    return w


if __name__ == "__main__":
    print(made_of_prime(made_of(140)))

# output: [2, 2, 5, 7]

话虽如此，我同意你的观点，即代码“未优化”。 未来的读者应该注意到，这是探索性代码，远非 参考实现来查找素因数。

如何进一步优化超出了答案的范围。 不止一本关于寻找素数主题的书。