Как найти взаимно простые числа python

1

 def calculate_hcf(x, y): 
    if x > y: 
        smaller = y 
    else: 
        smaller = x 
    for i in range(1, smaller + 1): 
        if ((x % i == 0) and (y % i == 0)): 
            hcf = i 
    return hcf 
 x = int(input()) 
y = int(input()) 
z = int(input()) 
if x >= 1 and y >= 1 and z >= 1: 
     if calculate_hcf(x, y) == 1 and calculate_hcf(y, z) == 1 and calculate_hcf(x, z) == 1: 
        print("взаимно простые") 
     else: 
        print("не взаимно простые") 



  


                       
  

Через функцию

Мне нужна помощь, чтобы найти ошибки в этой функции:

def is_coprime(num_1, num_2):
    """Function that returns true if 2 integers are coprime. """
    if num_1 > num_2:
        small = num_2
    else:
        small = num_1
    for i in range(1, small + 1):
        if ((num_1 % i == 0) and (num_2 % i != 0)):
            gcd = i
        if (gcd == 1):
            return True
        else:
            return False

Надеюсь, отступ не так уж и плох. Я думаю, что моя ошибка заключается в условии if, но я не могу понять, в чем именно.

Я бы предложил этот подход:

def divisors(x):
    return {i for i in range(2, x//2 + 1) if not x % i}

def coprime(x, y):
    return divisors(x).isdisjoint(divisors(y))

Как это работает? divisors (x) возвращает множество f всех делителей числа больше 1. Функция coprie (x, y) проверяет, не пересекаются ли заданные множества.

Coprime можно сделать с помощью math.gcd следующим образом:

import math

def is_coprime(x, y):
    return math.gcd(x, y) == 1

is_coprime(39, 115)
True

is_coprime(115*89,115)                                                                                                                             
False

Я бы сказал, что ваш алгоритм плохой. Давайте рассмотрим простой пример, сначала предположим:

num_1 = 2
num_2 = 3
small = 2

Выполнение этих значений через ваш цикл:

for i in range(1, small + 1):
    if num_1 % i == 0 and num_2 % i != 0:
        gcd = i

Первая итерация:

i = 1
2 % 1 == 0 and 3 % 1 == 0

Вторая (и последняя) итерация:

i = 2
2 % 2 = 0 and 3 % 2 != 0
    gcd = 2

Неправильный ответ! НОД (2, 3) == 1

Предполагая, что вы не хотите использовать встроенный math.gcd(), как предлагает @oppressionslayer, мы можем найти GCD в Википедии и использовать рекурсивный двоичный алгоритм. Поскольку нам нужно только знать, являются ли числа взаимно простыми, мы можем сократить одно из операторов этого алгоритма (тест на четность) и просто вернуть False:

def coprime(u, v):

    # simple cases (termination)
    if u == v:
        return u == 1

    if u == 0:
        return v == 1

    if v == 0:
        return u == 1

    # look for factors of 2
    if ~u & 1:  # u is even
        if v & 1:  # v is odd
            return coprime(u >> 1, v)

        return False

    if ~v & 1:  # v is even, u is odd
        coprime(u, v >> 1)

    # reduce larger argument
    if u > v:
        return coprime(u - v, v)

    return coprime(v - u, u)

Несколько простых тестов:

print(coprime(2, 3))  # True
print(coprime(21, 24))  # False
print(coprime(39, 115))  # True
print(coprime(115*89, 115))  # False