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

Question

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

1. find_factors功能
2. [is_prime功能-使用find_factors功能
3. [hcf功能-使用is_prime功能

[前两个函数返回因子和素数，并且is_prime函数正在使用我们的讲师要求的find_factors函数。

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 range(2,find_factors(x)):
            if x % a == 0:
                return False
    return True

接下来，我们被要求在此is_prime函数中使用hcf函数来查找HCF。如何在第三个is_prime功能中使用第二个hcf功能？

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 

甚至有可能从正常素数中找到HCF吗？也许我们的讲师是指prime factorization？

Answer 1

例如，您的find_factors返回数字的所有除数。然后，您可以只检查x和y的所有公共除数，并取将成为除数的最大值。从技术上讲，您不需要is_prime功能。

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

一个简单的版本：

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

Answer 2

将is_prime和find_factors用于hcf

代码

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

  return factors

def is_prime(x):
    if x < 2:
        return False
    else:
      # prime if only factors are 1 and itself
      # i.e. length factors equals 2
      return len(find_factors(x))==2 

def hcf(a, b):
  if a == b:
    return a
  elif is_prime(a) and is_prime(b):
    return 1

  # We know factors are in ascending order
  # based upon how the list are generated
  f_a = find_factors(a)
  f_b = find_factors(b)

  for num in f_a[::-1]: # go in reverse order
                        # to get the highestest number first
    if num in f_b:     
      return num        # Found if in other list

Test

for a, b in [(5, 15), (2, 3), (24, 8)]:
    print(f'For {a} & {b}, hcf = {hcf(a, b)}')

输出

For 5 & 15, hcf = 5
For 2 & 3, hcf = 1
For 24 & 8, hcf = 8