Задача
Даны целые числа [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 |
Код программы
Код программы на С++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> using namespace std; unsigned long gcd(unsigned long x, unsigned long y) { return (y!=0) ? gcd(y,x%y) : x; } int main() { unsigned int q = 0, p; cin >> q >> p; for (unsigned int i = 1; i <= q; i++) { if((q % i) == 0) { if (gcd(i,p) == 1) cout << i << " "; } } return 0; } |
Код программы на Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) throws java.lang.Exception { int q = 0, p; Scanner in = new Scanner(System.in); q = in.nextInt(); p = in.nextInt(); for (int i = 1; i <= q; i++) { if((q % i) == 0) { if (gcd(i,p) == 1) System.out.print(i + " "); } } } public static long gcd(long x, long y) { return (y!=0) ? gcd(y,x%y) : x; } } |
Решение
Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть [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)
— Пожалуйста, уберите символы кириллицы из постоянной ссылки.
— Описание решения не соответствует условию задачи. Вам нужно напечатать все делители одного числа, взаимнопростые с другим. Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1.
— Сделайте правильные отступы.
Исправила.
Иванна! Давайте вместе прочтём это Ваше предложение:
Для нахождения всех делителей целого числа нужно разложить данное число на простые множители, получаем каждый полученный простой множитель, находим всевозможные произведения всех полученных простых множителей между собой и добавляем в качестве делителя 1.
Мне оно кажется очень-очень неудачным и с точки зрения языка, и с точки зрения смысла. Попробуйте построить несколько коротких предложений с понятным и конкретным смыслом.
Исправила.
Хорошо. Давайте попробуем иначе. Я вместо Вас описал работу основной программы.
Вам остаётся описать Вашу рекурсивную реализацию алгоритма Евклида.
Проверьте, пожалуйста, дополнила.
Зачтено.
Хотя, я бы не включал единицу в число взаимно простых делителей. Когда говорят о простых числах, имеют ввиду натуральные числа больше 1. Но не буду настаивать.