개발 공부 - 유클리드 호제법을 이용한 최대공약수

큰 쪽에서 작은 쪽을 계속 빼는 형태의 최대공약수

/* Online Java Compiler and Editor */

public class HelloWorld{

    //

     public static void main(String []args){

        System.out.println("Hello, World!");

        int i = 50;

        int j = 30;

        int cnt = 0;

        while(i!=j){

            cnt++;

            if(i > j){

                System.out.println(cnt + "!   "+i+"  "+j);

                i -= j;

            }else{

                System.out.println(cnt + "    "+i+"  "+j);

                j -= i;

            }

        }

        

        System.out.println(i);

        

     }

}

큰 쪽에서 작은 쪽을 나눈 나머지를 계속 구하는 최대공약수 (더 효율적인 유클리드 호제법)

/* Online Java Compiler and Editor */

public class HelloWorld{

    //

     public static void main(String []args){

        System.out.println("Hello, World!");

        int i = 15;

        int j = 50;

        int cnt = 0;

        while(i!= 0 && j!=0){

            cnt++;

            if(i > j){

                i = i%j;

            }else{

                j = j%i;

            }

        }

        

        System.out.println(cnt + "    "+i+"  "+j);

        if(i == 0){

            System.out.println(j);

        }else{

            System.out.println(i);

        }

        

     }

}