наименьшие общие делители

Question

Я пытаюсь написать рекурсивную функцию, которая возвращает наименьший общий делитель или, например, возьмем 150 и 125, наибольший общий делитель равен 25, а наименьший общий делитель - 5. Еще раз мне нужна рекурсивная функция в прямом методе это тривиально.

Answer 1

Проверяйте каждое число до sqrt(min(a, b)): если числа делятся на него, вы его нашли.Вы можете проверять только простые числа, если хотите.

Если вы не нашли ни одного такого числа, то проверьте, кратно ли другое число минимальному: если да, то минимальное из двух - решениеВ противном случае, нет решения.

Вы можете сделать лучше.Вы можете идти только до sqrt(gcd(a, b)).Это должно быть достаточно быстро.

Answer 2

Если вы хотите найти least common factor элементов массива, вы можете сначала вычислить GCD всех элементов, а затем найти least prime factor из GCD полученных ...

чтобы получить gcd всех элементов массива: -

g=arr[0];
for(i=1;i<arr.length();i++)
   g=gcd(g,arr[i]);

сейчас, чтобы получить цикл наименьшего простого множителя до sqrt(g)

for(i=2;i<=sqrt(g);i++)
  if(g%i==0)
    return g

Answer 3

Реализация Python:Вышеупомянутое решение не будет работать для этих чисел 5 и 10, где наименьший общий делитель равен 5, поэтому здесь не работает квадратный корень