Is it possible to use prime numbers (not prime factorization), to find GCD?

Question

I have a code challenge that asks us to create 3 functions using the previous function. We are using "base python" so no imports. Versions without lambdas would be ideal, but both are welcome.

1. find_factors function
2. is_prime function - using the find_factors function
3. hcf function - using the is_prime function

The first two functions return the factors and prime numbers and the is_prime function is using the find_factors function as our instructor asked.

def find_factors(num):
    factors = []
    for i in range(1,num+1):
        if num%i==0:
            factors.append(i)
    return factors


def is_prime(x):
    if x < 2:
        return False
    else:
        for a in (find_factors(x):
            if x % a == 0:
                return False
    return True

Next we were asked to use the is_prime function in this hcf function to find the HCF.
How do I use the second is_prime function in this third hcf function?

def hcf(x, y): 
    if x > y: 
        small = y 
    else: 
        small = x 

    for i in range(1, small+1): 
        if((x % i == 0) and (y % i == 0)): 
            hcf = i   
    return hcf 

Is it even possible to find HCF from normal primes? Maybe our instructor meant prime factorization?

Answer 1

Let's say, your find_factors return all the divisor of a number. Then, you can just check the all common divisor for both x and y, and take the max that would be the divisor. Technically, you don't need the is_prime function.

For example,

If we have 12, and 4. Let's find the factors first. We will get them in a sorted manner from find_factors.

12 has factors: 1, 2, 3, 4, 6, 12

4 has factors: 1, 2, 4

possible solution set = [1, 2, 4] (the common ones only)

GCD or greatest common divisor will be only the maximum common number from both lists. So, the answer is 4.

def find_factors(num):
    divs = []
    for value in range(1, num + 1):
        if num % value == 0:
            divs.append(value)
    return divs

def hcf(x, y):
    divx = find_factors(x)
    divy = find_factors(y)
    pos_sol = set(divx).intersection(divy)
    return max(pos_sol)

print(hcf(56, 12)) 

A simpler version:

def find_factors(num):
    divs = []
    for value in range(1, num + 1):
        if num % value == 0:
            divs.append(value)
    return divs

def is_prime(x):
    if x < 2:
        return False
    else:
        for a in range(2,x-1): # technically you can go upto sqrt(n) but if math is allowed 
            if x % a == 0:
                return False
    return True

def hcf(x, y):
    if is_prime(x) and is_prime(y):
        return 1

    divx = find_factors(x)
    divy = find_factors(y)
    pos_sol = [x for x in divx if x in divy]
    return max(pos_sol)

print(hcf(4, 12))