Функция Python, которая возвращает true, если 2 целых числа взаимно просты

#python #primes #number-theory

#python #простые числа #теория чисел

Вопрос:

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

 
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-условии, но я не могу понять, в чем.

1. Вероятно, это лучший вопрос при обзоре кода

2. Можете ли вы исправить отступ?

3. «Надеюсь, отступ не так уж плох» — это Python, отступ имеет решающее значение 🙂

4. Если у вас есть конкретная проблема с кодом, вам следует отредактировать это в вопросе. В настоящее время вы не указываете, в чем собственно проблема.

5. «чтобы найти мои ошибки» — пожалуйста, добавьте пример ввода и ожидаемый результат, чтобы увидеть, где находятся ошибки

Ответ №1:

Взаимно простое число может быть выполнено с помощью 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

Ответ №2:

Я бы предложил такой подход:

 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) возвращает набор из всех делителей числа, большего 1.
Функция coprie(x, y) проверяет, являются ли заданные множества непересекающимися.

Ответ №3:

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

 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

Неправильный ответ! Gcd(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 amp; 1:  # u is even
        if v amp; 1:  # v is odd
            return coprime(u >> 1, v)

        return False

    if ~v amp; 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