最大公約数最小公倍数

私の数学はずっとごみで、150分の问题、高校の3年、150分の问题、めったに90の情况に行くことがなくて、99%は70分の上下でぶらぶらして、ああ、耻ずかしいです.これは直接私の数学に対する恐怖を招いて、卒業してからプログラミングの道を歩いて、やはり多くのアルゴリズムがあることを発見して、アルゴリズムに出会うたびに私は馬鹿で、ここはただ私のいくつかの小さい記録で、自分の頭に穴を開けましょう.
1、最大公約数を求める:
整数x,yがあると仮定して、この2つの数の最大公約数を要求します.どうすればいいですか.まず構想分析:まずxとyの中の小さい数iを求めて、それからiから0まですべての整数を循環して、最初のxとyによって除去することができる数は最大公約数です.

def gcd(x,y)
   i = x#  x           ，    i
   if x > y
      i = y#  y x ，   y   i
   end
   while i > 0 # i    ，     ，i     ，  i  0，           
      if x % i == 0 and y % i == 0
         return i #           x y  ，            
      else
         i -= 1#          x y，           x y，    
      end
   end
end

以上の考えはもう整理しましたが、複雑すぎて、短くしてもらえませんか.

def gcd2(x, y)
   i = x
   i = y if x > y
   #i.downto(1)   i(          )   0，     ，       ，      block，  block      ，        
   i.downto(1) {|j| return j if x%j==0 and y%j==0}
end

もう少し短くしてもらえませんか.

def gcd3(x,y)
   #        ，downto            ，                 
   (x+y).downto(1) {|j| return j if x%j==0 and y%j==0}
end

上のアルゴリズムは結果を求めることができるが、効率は最も低いはずだが、実はGCDを求める最も速いアルゴリズムとして公認されているアルゴリズムがある.
「転がり相殺法」 :
転がり相除算法は、2つの正の整数aおよびbの最大公約数を決定するために、以下の性質を利用する.
1.rがa÷bの剰余であれば、gcd(a,b)=gcd(b,r)
2.aとその倍数の最大公約数はaである

def gcd4(x,y)
   while y != 0#    ，  y!=0       
      r = x % y#r  x  y   
      x = y # y   x
      y = r #      y，  y，           0，     
   end
   return x
end

速くて短くてもいいですか.
再帰に変更すると、以下のように簡単に書くことができます.

def gcd5(x,y)
   x,y = y,x if x<y#      x，     y
   y==0 ? x : gcd5(x%y, y)#     0，               ，  ，         
end

上の書き方は2行しかありませんが、少し多い感じがします.xとyを比較してもいいですか.

def gcd6(x, y)
   y == 0 ? x : gcd6(y, x%y) #  r   a ÷ b    ,  gcd(a,b) = gcd(b,r)
end

最小公倍数:
これまで最小公倍数LCMについては言及されていなかった.ずっと言わないのは、不思議な公式があるからだ.

GCD * LCM = x * y

gcdでlcmを計算することができます

def lcm(x,y)
   x * y / gcd(x,y)
end

もし私が1行のコードで書くように要求したら、2つの数の最小公倍数を求めてどう書きますか.
例えば6と9の最小公倍数を要求します.

#       x y，              1 x*y  ，               ，               x    0         y    0，             
1.upto(6*9){|j| return j if j%6 == 0 && j%9 == 0 }