是否可以使用质数（而不是质因数分解）来查找GCD？

由 发布于 pythonprimesgreatest-common-divisorprime-factoring
 收藏

我遇到一个代码挑战，要求我们使用上一个函数创建3个函数。我们正在使用“基本python”，因此没有导入。没有lambda的版本将是理想的，但是都欢迎使用。

  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):
    for value in range(1, num + 1):
        if num % value == 0:
            print("{0}".format(value))
    return num


def is_prime(x):
    if x < 2:
        return False
    else:
        for a in range(2,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?

评论