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)

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

  1. — Пожалуйста, уберите символы кириллицы из постоянной ссылки.
    — Описание решения не соответствует условию задачи. Вам нужно напечатать все делители одного числа, взаимнопростые с другим. Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1.
    — Сделайте правильные отступы.

  2. Иванна! Давайте вместе прочтём это Ваше предложение:
    Для нахождения всех делителей целого числа нужно разложить данное число на простые множители, получаем каждый полученный простой множитель, находим всевозможные произведения всех полученных простых множителей между собой и добавляем в качестве делителя 1.
    Мне оно кажется очень-очень неудачным и с точки зрения языка, и с точки зрения смысла. Попробуйте построить несколько коротких предложений с понятным и конкретным смыслом.