Python: Finding GCD using Middle School Procedure

Question

Middle School Procedure GCD

• Step 1 Find the prime factors of m.
• Step 2 Find the prime factors of n.
• Step 3 Identify all the common factors in the two prime expansions found in Step 1 and Step 2. (If p is a common factor occurring pm and pn timesin m and n, respectively, it should be repeated min{pm, pn} times.)
• Step 4 Compute the product of all the common factors and return it as the greatest common divisor of the numbers given.

Thus, for the numbers 60 and 24, we get

60 = 2 . 2 . 3 . 5

24 = 2 . 2 . 2 . 3

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

So using the above instructions, this is what I got so far:

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))

I know the last part is wrong but I have no idea how to fix it. The instructions said something about repeating the f to a minimum but I'm clueless. Please help.

Answer 1

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()))

Or you can also do it in a one liner:

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