JavaScript

Ищу НОД (js), как можно ускорить цикл? з. ы. Я только учусь=)

Function nod(x,y) {
let count=1;
for (let i=1; i<x || i<y; i++) {
if (x%i==0 && y%i==0) {
count=i;
} else {
continue;
}
}
return count;
}
Aibek .
Aibek .
502
ускорить цикл можно переносом кода на YoptaScript. Подробнее на yopta.space
Владимир Котельников
Владимир Котельников
27 730
Лучший ответ
Достаточно продолжать цикл только до sqrt(min(x, y)):

function nod(x, y) {
let res = 1;
if (x > y) { [x, y] = [y, x]; }
for (int i = 1; i * i <= x; ++i) {
if (x % i) { continue; } // x не делится на i
if (y % (x / i) == 0) { return x / i; } // подошёл больший делитель
if (y % i == 0) { res = i; } // подошёл меньший делитель.
}
return res;
}

Всегда x <= y.
Если x делится на i, имеем 2 делителя: i и x / i, причём x / i >= i. Если y делится на x / i - сразу возвращаем x / i, т. к. это гарантировано НОД.

Но, разумеется, алгоритм Евклида быстрее и короче:

function nod(x, y) {
while (x) { [x, y] = [y % x, x]; }
return y;
}
Ускорить цикл можно, если не импровизировать и не использовать перебор, а воспользоваться традиционным алгоритмом Эвклида.
Игорь Гущин
Игорь Гущин
79 206
Aibek . Благодарю за Эвклида, задачку удалось ускорить с его помощью, но можно ли как-то ускорить код с перебором?
Конкретно этот цикл можно записать так:

function nod(x, y) {
  if (x > y) [x, y] = [y, x];
  // Гарантирует, что x меньше.

  let div = y / x;
  if ((div | 0) == div) return x;
  // Если и так делится нацело, сразу возвращает меньшее число без перебора

  let count = 1, stop = x / 2;
  // Точно не делится, значит делитель как минимум будет меньше или равен x / 2
  // количество итераций сократится вдвое.

  for (let i = 1; i <= stop; i++) {
    if (x % i + y % i == 0) {
      count = i;
    }
  }

  return count;
}
_________

i<x || i<y; — выкинул две проверки, сразу можно определить меньшее и перебрать до него.

else { continue } — бессмысленно, т. к. основной код и так заключен в if, а после него нет другого кода.

Можно еще подумать, для двух случайных чисел наибольший делитель чаще оказывается ближке к маленьким числам или большим, при необходимости начинать цикл сверху вниз.
Лё}{@ - $H@\/@$H0\/
Лё}{@ - $H@\/@$H0\/
62 360
Aibek . Благодарю за ответ =) Буду экспериментировать.