Python:使用 Middle School Procedure 查找 GCD

Question

中学程序 GCD

• 第 1 步找到 m 的质因数。
• 第 2 步找到 n 的质因数。
• 第 3 步确定两个素数展开式中的所有公因子在第 1 步 和第 2 步 中找到。 (如果 p 是发生在 pm 和pn次分别为m和n，应该重复min{pm, pn}次。)
• 第 4 步计算所有公因数的乘积并将其返回为给定数字的最大公约数。

因此，对于数字 60 和 24，我们得到

60 = 2 。 2. 3. 5

24 = 2 。 2. 2. 3

gcd(60, 24) = 2 。 2. 3 = 12。

所以使用上面的说明，这是我到目前为止得到的:

import numpy as np

#find prime factors of m and output it to list fm
def Middle(m,n):
    c = 2
    fm = [ ]  
    while m > 1:
      if m % c == 0:
        fm.append(c)
        m = m/c
      else:
        c = c + 1             
    return fm

#find prime factors of n and output it to list fn
    d = 2
    fn = [ ]  
    while n > 1:
      if n % d == 0:
        fn.append(d)
        n = n/d
      else:
        d = d + 1 
    return fn

#compare fm and fn and multiply common items
#this is the part where I got wrong       
    cf = []
    for f in fm:
        if f in fn:
            cf.append(f) 
    return (np.prod(cf))

我知道最后一部分是错误的，但我不知道如何修复它。说明说了一些关于将 f 重复到最低限度的内容，但我一无所知。请帮忙。

Answer 1

这是获得所需输出的一种方法:

import functools
def gcd(a,b):
    def factArr(x):
        list = []
        i=2
        while i <= x:
            if (x % i) == 0:
                list.append(i)
                x = x/i
                i = 2
            else:
                i = i+1
        return list
    aArr = factArr(a);
    bArr = factArr(b);
    print("aArr",aArr,"bArr",bArr)
    cArr = []
    for v in aArr:
        if v in bArr:
            cArr.append(v)
            bArr.remove(v)
    print("cArr",cArr)
    return functools.reduce(lambda x, y: x*y, cArr)
gcd(60,24)`