Взаимно простые числа

В этом примере рассматривается реализация алгоритма поиска взаимно простых наборов чисел (Coprimes) на языке Julia, который фильтрует наборы чисел, оставляя только те, где все числа взаимно просты (их НОД равен 1).

Введение

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

Основная часть

Подготовка данных

Сначала мы определяем список наборов чисел, которые будем проверять на взаимную простоту. Каждый подсписок — это набор чисел, НОД которых мы хотим проверить.

# Исходные данные: список наборов чисел
data = [[21,15],[17,23],[36,12],[18,29],[60,15],[21,22,25,31,143]]

6-element Vector{Vector{Int64}}:
 [21, 15]
 [17, 23]
 [36, 12]
 [18, 29]
 [60, 15]
 [21, 22, 25, 31, 143]

Теперь применим фильтрацию к этим данным. Для этого используем функцию filter, которая оставит только те наборы, для которых выполняется условие: наибольший общий делитель всех чисел в наборе равен 1.

# Фильтрация: оставляем только наборы, где НОД всех чисел равен 1
# p — это один набор чисел (например, [21, 15])
# gcd(p...) — вычисляет НОД всех чисел в наборе, разворачивая его через "splat" (...)

coprime_sets = filter(p -> gcd(p...) == 1, data)

3-element Vector{Vector{Int64}}:
 [17, 23]
 [18, 29]
 [21, 22, 25, 31, 143]

Разберём выражение gcd(p...) подробнее:

p — это массив чисел, например, [21, 15].
p... — это оператор "splat", который разворачивает массив в отдельные аргументы. То есть gcd([21, 15]...) превращается в gcd(21, 15).
gcd — стандартная функция Julia, вычисляющая наибольший общий делитель.

Результат работы

В результате работы алгоритма получаем список только тех наборов чисел, в которых все числа взаимно просты. Взаимная простота означает, что НОД всех чисел в наборе равен 1.

# Вывод результата
println("Взаимно простые наборы:")
for set in coprime_sets
    println(set)
end

Взаимно простые наборы:
[17, 23]
[18, 29]
[21, 22, 25, 31, 143]

Заключение

В этом примере мы реализовали алгоритм поиска взаимно простых наборов чисел, который фильтрует наборы чисел, оставляя только те, где все числа взаимно просты. Это полезно в задачах, где важно, чтобы числа не имели общих делителей, например, в криптографии или при работе с дробями. Мы использовали встроенные функции Julia: filter, gcd и оператор ... для распаковки аргументов.

Пример разработан с использованием материалов Rosetta Code

Взаимно простые числа