A324. Делители одного числа, взаимно простые с другим

Задача

Даны целые числа [latex]p[/latex] и [latex]q[/latex]. Получить все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex].

Тесты

[latex]q[/latex] [latex]p[/latex] Все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex]
40 15 1 2 4 8
87 3 1 29

Код программы

Код программы на С++

Код программы на Java

Решение

Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть [latex]m[/latex] и [latex]n[/latex] — не равные нулю целые неотрицательные числа, и пусть [latex]m\geq n[/latex]. Тогда, если [latex]n=0[/latex], [latex]GCD(n,m)=m[/latex], а если [latex]n\neq 0[/latex], то для числе [latex]m[/latex], [latex]n[/latex] и [latex]k[/latex], где [latex]k[/latex] — остаток от деления [latex]m[/latex] и [latex]n[/latex], выполняется равенство [latex]GCD(m,n)=GCD(n,k)[/latex].
Для нахождения делителей числа [latex]q[/latex] взаимно простых с [latex]p[/latex], программа проверяет остатки от деления [latex]q[/latex] на все числа [latex]i[/latex] от [latex]1[/latex] до [latex]q[/latex]. Если остаток равен нулю, то число [latex]i[/latex] является делителем [latex]q[/latex]. Для каждого такого числа выполняется поиск наибольшего общего делителя (НОД — Greatest common divisor, GCD) [latex]i[/latex] и [latex]p[/latex] по алгоритму Евклида. Если найденный наибольший делитель равен 1, то числа [latex]i[/latex] и [latex]p[/latex] взаимно простые.

Ссылки

Условие задачи
Решение задачи на сайте Ideone.com (C++)
Решение задачи на сайте Ideone.com (Java)

Related Images: