Задача
Даны целые числа [latex]p[/latex] и [latex]q[/latex]. Получить все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex].
Тесты
| q | p | Все делители числа q, взаимно простые с числом p |
| 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 18 19 20 21 22 23 24 25 |
import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Ideone { public static long gcd(long x, long y){ return (y != 0) ? gcd(y, x%y) : x; } public static void main (String[] args) { 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.println(i + " "); } } } } |
Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть m и n — не равные нулю целые неотрицательные числа, и пусть [latex]m\geq n[/latex]. Тогда, если [latex]n=0[/latex], [latex]GCD(n,m)=m[/latex], а если [latex]n\neq 0[/latex], то для чисел [latex]m,n[/latex] и [latex]k[/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] по алгоритму Евклида. [latex]1[/latex], то числа [latex]i[/latex] и [latex]p[/latex] взаимно простые.