math/gcd.ts at master · YungDice/math · GitHub

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
export function gcdBruteForce(a: number, b: number): number {
  let left = Math.abs(a);
  let right = Math.abs(b);

  if (left === 0 && right === 0) {
    return 0;
  }
  if (left === 0) {
    return right;
  }
  if (right === 0) {
    return left;
  }

  const min = Math.min(left, right);
  for (let i = min; i >= 1; i--) {
    if (left % i === 0 && right % i === 0) {
      return i;
    }
  }

  return 1;
}

export function gcdEuclid(a: number, b: number): number {
  const left = Math.abs(a);
  const right = Math.abs(b);

  if (left === 0) {
    return right;
  }
  if (right === 0) {
    return left;
  }
  if (left === right) {
    return left;
  }

  if (left > right) {
    return gcdEuclid(left - right, right);
  }
  return gcdEuclid(left, right - left);
}