ユークリッドアーク除去法(最大公約数を求める)+最小公倍数>feat.BOJ 2609

6691 ワード
algorithm js テキストリンク

定義＃テイギ＃


ユークリッド相互除去法は2つの自然数または式の最大公因子を求めるアルゴリズムの1つである.
相互除算法とは、2つの数が相互除算によって最終的に所望の数を得るアルゴリズムである.
2つの自然数(または正式)a,bについて、aをbで割った残りの数をr(ただし、a>b)と呼ぶと、aおよびbの最大公約数はbおよびrの最大公約数に等しい.
この性質に基づいて、bをrの残りのr’で割って、rをr’の残りの過程で割って、残りが0の時、除いた数はaとbの最大公約数です.
これも明示的に記述された最古のアルゴリズムで、紀元前300年ごろのユークリッドの「原論」第7巻に相当し、命題は1から3である.
-ウィキペディア、私たち全員の百科事典.
最も良い方法は断章して意味を取り、観覧を示すことだ.
78696(a) ＝ 19332(b)×4 ＋ 1368(a%b)
19332(a) ＝ 1368(b)×14 ＋ 180(a%b)
 1368 ＝ 180×7 ＋ 108
  180 ＝ 108×1 + 72
  108 ＝ 72×1 ＋ 36
   72 ＝ 36×2 >> 나머지가 0이 되었을 때 나누는 수가 최대공약수

BOJアルゴリズム問題2609

// let fs = require('fs');
// let stdin = fs.readFileSync('/dev/stdin').toString().trim().split(' ');

const fs = require('fs');
 const stdin = (
   process.platform === 'linux'
     ? fs.readFileSync('/dev/stdin').toString()
     :`24 18`).trim().split(' ');

let a = stdin[0]
let b = stdin[1]

//위의 예시처럼 a를 b로 나눴을 때 나머지가 0이 아닐 경우 extra에 나머지 값을 넣어두고 a는 b로 b는 이 나머지 값을 다시 바꿔서 반복문을 돌리다가 else(=나머지가 0일 때 b의 값을 최대공약수로 바꾼다.
while (a%b!== 0) {
  let extra = a%b;
  if(a%b!==0) {
    a=b
    b=extra
  } else {
    b=extra
    break
  }
}

let min = (stdin[0]*stdin[1])/b
console.log(b)
console.log(min)

最小公倍数

(a*b)/최대공약수
Level 1. 模擬試験
Riotjsのいいところ