컴퓨터 엑셀 워드 포토샵 구글어스 WINDOWS JAVASCRIPT JAVA C++

 
Friday, March 16, 2007

Java 자바] 최대 공약수 구하기 함수; gcd, Greatest Common Divisor Method


다른 프로그래밍 언어들도 그렇지만 자바에도, 최대 공약수를 구하는 메서드(함수)가 없어서 직접 만들어 주어야 합니다. "Euclidean Algorithm; Euclid's Algorithm" 이라는 알고리즘으로 메서드를 만들었습니다.

최대공약수는 보통 gcd 라고 합니다. Greatest Common Divisor 의 약자입니다.

둘 이상의 정수들이 있고, 그 정수들을 어떤 숫자로 동시에 나누었을 때, 나머지가 없이 딱 나누어 떨어지는 숫자들이 몇 개 있을 것입니다. 그 숫자들 중에서 가장 큰 양수를 최대공약수라고 합니다. 분수의 약분에 사용됩니다.

예를 들어, 12와 18의 최대 공약수는 6인데,
6으로 12와 18을 나누면 나머지가 없이 딱 떨어집니다.

6은 {1, 2, 3, 6} 으로 나누어 떨어지고
18은 {1, 2, 3, 6, 9, 18} 로 나누어 떨어지지만

공통되는 약수 즉 공약수 중에서 가장 큰 숫자는 6입니다.

최대공약수 계산 예제 소스


소스 파일명: Example.java
public class Example {
  public static void main(String[] args) {

    System.out.println(gcd(12, 18));
    // 6

    System.out.println(gcd(5154, 3435));
    // 3

    System.out.println(gcd(0, 0));
    // 0
    // 이 경우는 0으로 정의되어 있음

    System.out.println(gcd(1, 0));
    // 1
    // 이것도 맞습니다.

    System.out.println(gcd(0, 12));
    // 12
    // 이것도 맞습니다.

    System.out.println(gcd(13, 12));
    // 1
    // 공약수가 1밖에 없는 '서로소(Relatively Prime; Coprime)'임

    System.out.println(gcd(-42, -56));
    // 14
    // 최대공약수는 항상 양수임

    // 세 가지 수의 최대공약수 구하기
    System.out.println(gcd(gcd(42, 12), 48));
    // 6

  }




  public static int gcd(int a, int b) {
    while (b != 0) {
      int temp = a % b;
      a = b;
      b = temp;
    }
    return Math.abs(a);
  }


}



▶▶ 자바 Java, 최소공배수 구하기 함수; LCM; Least Common Multiple


최대공약수 온라인 계산기: ▶▶ 최대공약수 계산기; GCD 구하기 Calculator




tag: java
자바 | Java
tag: study
학습 | Study

0 Comments:

Post a Comment

<< Home RSS 2.0 feed

구글 Google 에서 제공하는 무료 블로그 서비스인 블로거 Blogger 의 인터넷 주소는 www.blogger.com 입니다. Blogger 에 블로그를 만들면, blogspot.com 이라는 주소에 블로그가 생성됩니다.
블로그를 직접 방문하지 않고도 최신 게시물을 구독하려면 RSS 2.0 feed 주소를 리더기에 등록하시면 됩니다.
Previous Posts
Monthly Archives
Top