【Network Security】最大公因數GCD（A，B）演算法－ALOHA JESSIE

Oct 22 Wed 2008 23:27
【Network Security】最大公因數GCD（A，B）演算法

最大公因數GCD（A，B）演算法

GCD（A , B）= GCD（B , A mod B）

已知：A，B
求：GCD（A , B）

Step1：If B = 0, then return 4
Step2：R ← A mod B
            A ← B
            B ← R
Step3：Goto Step1

EX：GCD（552 , 234）
Ans：GCD（552, 234）=GCD（234 , 84）=GCD（84 , 66）
       =GCD（66 , 18）=GCD（18 , 12）=GCD（12 , 6）=GCD
       （6 , 0）= 6