【ユークリッドの互除法】2つの値の公約数のうち、n 番目に大きい数値を高速に求める

ふたつの値 A も B も割り切れる値の中から n 番目（K）に大きい数値を求める場合、一般的には以下のように書くことで求められる。

const input = "50 100 4"

const main = (input: string) => {
  const [A, B, K] = input.split(" ").map(str => parseInt(str))
  let divisorList = [];

  for (let i = A; i > 0; i--) {
    if(A % i === 0 && B % i === 0) {
      divisorList.push(i)
    }
  }
  console.log(divisorList[K - 1])
}

main(input);

ループの中でそれぞれの約数を求め、配列に突っ込んでいる。
今回の条件はn 番目に大きい数値を求めるため、配列には大きな数値から並ぶようにしている。

ユークリッドの互除法

ユークリッドの互除法というものを使えばもっと高速に処理することも可能。
ユークリッド互除法は最大公約数を簡単に高速に求めることが可能な方法。
Javascriptで最大公約数を求める(ユークリッドの互除法)

これを使って最大公約数を求めてから、その約数を列挙することでNの約数列挙はO(√N)で済むため、プログラムが高速になる。（ループの回数が極端に減る）

const input = "50 100 4"

const main = (input: string) => {
  const [A, B, K] = input.split(" ").map(str => parseInt(str))
  let divisorList = [];

  const calcGcd = (a: number, b: number): number => {
    const r = a % b;
    if(r === 0) {
      return b;
    }
    return calcGcd(b, a % b)
  }

  const gcd = calcGcd(A, B)

  for (let i = gcd; i > 0; i--) {
    if(gcd % i === 0) {
      divisorList.push(i)
    }
  }

  console.log(divisorList[K - 1])
}

main(input);

さらにこれだと A === B であるときはループの回数が変わらないので、約数の列挙を以下の記事を参考に修正してみる。(記事は Python)

約数を高速で列挙するコード(Python)

const input = "50 100 4"

const main = (input: string) => {
  const [A, B, K] = input.split(" ").map(str => parseInt(str))
  let divisorList = [];

  const calcGcd = (a: number, b: number): number => {
    const r = a % b;
    if(r === 0) {
      return b;
    }
    return calcGcd(b, a % b)
  }

  const gcd = calcGcd(A, B)
  const squareRoot = Math.ceil(Math.sqrt(gcd))

  for (let i = squareRoot; i > 0; i--) {
    if(gcd % i === 0) {
      divisorList.push(i)
      if(i !== gcd / i) {
        divisorList.push(gcd / i)
      }
    }
  }

  console.log(divisorList[K - 1])
}

main(input);

例えば 50 の約数を求めるときは 50 は 2 で割り切れるので、2 だけではなく、同時に 50/2 = 25 も約数であることがわかるので、わざわざ 1-50まで割り切らなくても、1-8まで割ることで全ての約数をカバーすることが可能になる。
そこで、

const squareRoot = Math.ceil(Math.sqrt(gcd))

ここでまず平方根を求めて整数化して for 文に渡している。

ただしこの方法だと約数の配列順序がバラバラになってしまうので、降順にソートして返す。

const input = "50 100 4"

const main = (input: string) => {
  const [A, B, K] = input.split(" ").map(str => parseInt(str))
  let divisorList = [];

  const calcGcd = (a: number, b: number): number => {
    const r = a % b;
    if(r === 0) {
      return b;
    }
    return calcGcd(b, a % b)
  }

  const compareFunc = (a: number, b: number) => {
    return b - a;
  }

  const gcd = calcGcd(A, B)
  const squareRoot = Math.ceil(Math.sqrt(gcd))

  for (let i = squareRoot; i > 0; i--) {
    if(gcd % i === 0) {
      divisorList.push(i)
      if(i !== gcd / i) {
        divisorList.push(gcd / i)
      }
    }
  }

  divisorList.sort(compareFunc)
  console.log(divisorList[K - 1])
}

main(input);

これで非常に高速に指定した約数を取得することができる。