是否可以使用素数（不是素数分解）来找到 GCD？

Question

我有一个代码挑战，要求我们使用之前的函数创建 3 个函数。我们正在使用 "base python" 所以没有导入。没有 lambda 的版本将是理想的，但两者都是受欢迎的。

find_factors 函数
is_prime函数-使用find_factors函数
hcf函数-使用is_prime函数

前两个函数 return 因子和质数，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 (find_factors(x):
            if x % a == 0:
                return False
    return True

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

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 吗？也许我们导师的意思是?

Answer 1

比方说，您的 find_factors return 一个数的所有除数。然后，您可以只检查 x 和 y 的所有公约数，并取最大值作为公约数。从技术上讲，您不需要 is_prime 函数。

例如，

如果我们有12，还有4。我们先求因数。我们将从 find_factors.

中以排序的方式获取它们

12 有因数：1、2、3、4、6、12

4 有因数：1、2、4

可能的解集=[1,2,4]（只有常见的）

GCD 或最大公约数将只是两个列表中的最大公约数。所以，答案是 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))

更简单的版本：

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

对 hcf 使用 is_prime 和 find_factors

代码

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

测试

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

是否可以使用素数（不是素数分解）来找到 GCD？

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

python

primes

prime-factoring

greatest-common-divisor