python - Python:使用中学程序查找GCD

中学程序GCD
第一步找出m的素因子。
第二步找出n的素因子。
步骤3确定两个素数展开中的所有公共因子
在Step 1和Step 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重复到最低限度，但我一无所知。请帮忙。

最佳答案

import numpy as np
from collections import Counter

# Find the prime factors of a integer
def prime_factors(n):
    factors = []
    i = 2
    while n > 1:
        if n % i == 0:
            factors.append(i)
            n /= i
        else:
            i += 1
    return Counter(factors)

# Find prime factors of m and n and multiply their common ones
def Middle(m, n):
    fm = prime_factors(m)
    fn = prime_factors(n)
    cf = fm & fn
    return np.prod(list(cf.elements()))

或者你也可以用一行代码：

def Middle(m, n):
    return np.prod(list((prime_factors(m) & prime_factors(n)).elements()))

关于python - Python:使用中学程序查找GCD，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47073426/