Security Akademeia

誊肌 †

誊肌
はじめに
ユ〖クリッドの高近恕
- Javaによる悸刘
ユ〖クリッドの高近恕における帆り手し搀眶
徊雇矢弗

はじめに †

　2つの腊眶の呵络给腆眶∈GCM∷を滇めるもっとも燎搜な数恕は、2,3,5,∧とmin(a,b)笆柒の燎眶について充っていくことである。充った冯蔡、2つの腊眶が充り磊れれば、その给腆眶にはその燎眶が崔まれるということを罢蹋する。つまり、呵络给腆眶はこうした燎眶のすべての齿け圭わせたものである。このアルゴリズムは肌の奶りである。

Input¨A,B∈10渴眶の腊眶∷
Output¨GCM∈AとBの呵络给腆眶∷

GCM=1
if min(a,b)″2 then
    exit
while 2|a ⑹ 2|b do
    a = a/2
    b = b/2
    GCM = GCM*2
if min(a,b)″3 then
    exit
while 3|a ⑹ 3|b do
    a = a/3
    b = b/3
    GCM = GCM*3
if min(a,b)″5 then
    exit
while 5|a ⑹ 5|b do
    a = a/5
    b = b/5
    GCM = GCM*5
∧∈min(a,b)笆布の燎眶についてすべて票屯に雇える∷∧

　ところが、このアルゴリズムでは、min(a,b)笆布のすべての燎眶のリストを脱罢しておかなければならない。これを豺疯するアルゴリズムのひとつがユ〖クリッドの高近恕である。

↑

ユ〖クリッドの高近恕 †

　ユ〖クリッドの高近恕では、燎眶を脱罢せずとも、どんな眶の呵络给腆眶でも滇めることができる。2,000钳笆惧涟にユ〖クリッドによって券斧されたアルゴリズムである。もっとも答塑弄なアルゴリズムともいえる。

　ユ〖クリッドの高近恕のアルゴリズムは肌の奶りである。

Input¨a,b∈0笆惧の腊眶∷
Output¨(a,b)∈aとbの呵络给腆眶∷

r[-2]a,r[-1]b,n0
if r[n-1]=0 then
    output r[n-2]
    return
else
    r[n]r[n-2]%r[n-1]
    nn+1
    goto 2乖誊

毋¨a=21,b=14の呵络给腆眶(a,b)をユ〖クリッドの高近恕を蝗って滇める。

n¨カウンタ〖のn
qn¨rn-2∴rn-1の途り

n	qn	rn
-2		21
-1		14
0	1	7
1	2	0
2

　搏咖の婶尸が介袋猛の掐蜗である。叫蜗冯蔡は、垮咖のように0となった改疥のひとつ惧である。よって、乐咖が呵络给腆眶であり、これが叫蜗される。

(21,14)=7

　このように燎傍眶尸豺をせずに帽に充り换をするだけで、呵络给腆眶が滇められるわけである。

↑

Javaによる悸刘 †

 
 
 
 
 
 
-
|
-
|
|
|
|
-
-
|
|
|
|
|
|
|
|
|
-
|
|
-
|
|
!
|
|
-
|
!
|
|
|
|
-
|
|
|
!
|
|
|
|
|
|
|
|
|
!
!
!

/*
 * ユ〖クリッドの高近恕で呵络给腆眶∈GCM∷と呵井给腆眶∈LCM∷を滇める
 * 掐蜗¨2つの腊眶
 * 叫蜗¨呵络给腆眶
 */
import java.io.*;
public class EuclidGCM {
 
    public static void main(String[] args){
        int a=0,b=0;
        
        //腊眶を掐蜗する
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            try{
                String line;
            
                System.out.println("腊眶a¨");
                line=rd.readLine();
                a=Integer.parseInt(line);
            
                System.out.println("腊眶b¨");
                line=rd.readLine();
                b=Integer.parseInt(line);        
            }catch(IOException e){
                System.out.println("掐蜗エラ〖");
                return;
            }catch(NumberFormatException e){
                System.out.println("腊眶を掐蜗してください。");
                continue;
            }
        
            //aまたはbが0なら姜位する
            if(a==0 || b==0){
                break;
            }
        
            //aとbを瘦赂しておく。
            int sa=a,sb=b;
            //充り磊れるまで帆り手す。
            while(b != 0){
                int r = a%b;
                a=b;
                b=r;
            }
            
            //呵井给腆眶を滇める
            int lcm = sa * sb / a;
        
            //呵络给腆眶を山绩する。
            System.out.println(sa + "と" + sb + "の呵络给腆眶は" + a + "です。");
            //呵井给腆眶を山绩する。
            System.out.println(sa + "と" + sb + "の呵井给腆眶は" + lcm + "です。");
            
        }
    }
}

　络腊眶におけるユ〖クリッドの高近恕のプログラム∈bigeuclid.java∷を肌に绩す。

 
 
-
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-
|
|
|
!
|
!
!

import java.io.*;
import java.math.BigInteger;
public class bigeuclid{
    public static void main(String[] args) throws Exception{
        BigInteger a,b,r,a1,b1;
 
        System.out.println("赖の腊眶a,bを掐蜗せよ。");
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(in);
 
        System.out.print("Input a = ");
        String s1=br.readLine();
        a = new BigInteger(s1);
 
        System.out.print("Input b = ");
        String s2=br.readLine();
        b = new BigInteger(s2);
 
        a1=a;
        b1=b;
 
        // bが0でないならば
        while(b.equals(BigInteger.valueOf(0)) == false){
            r=a.remainder(b);    // mod(a,b)
            a=b;
            b=r;
        }
        System.out.println("GCD(" + a1 + "," + b1 +")=" + a.toString());
    }
}