🔍 Как проверить, являются ли числа взаимно простыми в Python

Чтобы проверить, являются ли два числа взаимно простыми в Python, можно воспользоваться алгоритмом нахождения их наибольшего общего делителя (НОД). Если НОД равен 1, то числа являются взаимно простыми. Вот пример кода:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def are_coprime(a, b):
    return gcd(a, b) == 1

# Пример использования
num1 = 15
num2 = 28

if are_coprime(num1, num2):
    print("Числа", num1, "и", num2, "являются взаимно простыми.")
else:
    print("Числа", num1, "и", num2, "не являются взаимно простыми.")

Здесь мы определяем функцию gcd(a, b) для нахождения НОД двух чисел, и функцию are_coprime(a, b), которая проверяет, являются ли числа взаимно простыми. В примере мы проверяем числа 15 и 28. Если они взаимно простые, выводится сообщение "Числа 15 и 28 являются взаимно простыми.", в противном случае выводится сообщение "Числа 15 и 28 не являются взаимно простыми."

Как проверить, являются ли числа взаимно простыми в Python

Когда мы говорим о двух числах, которые являются взаимно простыми, мы имеем в виду, что их наибольший общий делитель (НОД) равен единице. В Python мы можем использовать различные методы и функции для проверки, являются ли два числа взаимно простыми. Давайте рассмотрим несколько подходов.

1. Нахождение НОД с помощью алгоритма Евклида

Алгоритм Евклида позволяет нам эффективно находить НОД двух чисел. Мы можем использовать этот алгоритм, чтобы проверить, являются ли числа взаимно простыми. Вот как это можно сделать:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def are_coprime(a, b):
    return gcd(a, b) == 1

# Пример использования
print(are_coprime(15, 28))  # Выводит: True
print(are_coprime(12, 18))  # Выводит: False
    

В этом примере мы определяем функцию gcd для нахождения НОД двух чисел, а затем определяем функцию are_coprime, которая возвращает True, если числа взаимно простые, и False в противном случае. Мы использовали алгоритм Евклида внутри функции are_coprime для вычисления НОД и проверки его равенства единице.

2. Использование функции math.gcd

В Python есть встроенная функция math.gcd, которая находит НОД двух чисел с помощью алгоритма Евклида. Мы можем использовать эту функцию для проверки, являются ли числа взаимно простыми. Вот пример:

import math

def are_coprime(a, b):
    return math.gcd(a, b) == 1

# Пример использования
print(are_coprime(15, 28))  # Выводит: True
print(are_coprime(12, 18))  # Выводит: False
    

В этом примере мы просто используем функцию math.gcd и проверяем, равен ли ее результат единице. Функция are_coprime возвращает True, если числа взаимно простые, и False в противном случае.

3. Проверка делителей чисел

Еще один способ проверить, являются ли числа взаимно простыми, - это проверить их делители. Если два числа не имеют общих делителей, кроме единицы, то они взаимно просты. Вот пример кода:

def are_coprime(a, b):
    for i in range(2, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            return False
    return True

# Пример использования
print(are_coprime(15, 28))  # Выводит: True
print(are_coprime(12, 18))  # Выводит: False
    

В этом примере мы используем цикл for, чтобы перебрать все числа от 2 до минимального из двух чисел. Если мы найдем какое-либо число, которое является делителем и для a, и для b, то функция вернет False. В противном случае, если ни одно число не обнаружится, функция вернет True.

Заключение

Теперь вы знаете несколько способов проверить, являются ли два числа взаимно простыми в Python. Вы можете использовать алгоритм Евклида, встроенную функцию math.gcd или проверять их делители. Все эти подходы дадут вам правильный ответ. Используйте тот, который вам удобнее и соответствует вашим требованиям.