최대 공약수(Greatest Common Divisor) 구하기

 

최대 공약수는 두 정수의 약수 중 가장 큰 수를 말한다. 최대 공약수를 구하는 방식을 통해 알고리즘에 대해 이해할 수 있다. 최대 공약수를 구하는 방법은 몇 가지가 있는데 순서대로 알고리즘을 풀어보자.

 

 

 

1. 순차적인 약수를 구해 최대 공약수를 찾아내는 방법 : 클래스 구성은 View와 모델을 하나로 합쳐 구성

import java.awt.Color;
import java.awt.Container;
import java.awt.FlowLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
import javax.swing.JTextField;

public class GetGCD extends JFrame implements ActionListener {

    private static final long serialVersionUID = 1L;
    private StringBuffer stringBuffer;
    private static int GCD = 0;
 
    private int x = 50;
    private int y = 50;
    private int width = 500;
    private int height = 300;
 
    private JLabel description;
    private JTextField first;
    private JTextField second;
    private JButton submit;
    private JTextArea area;
 
    private JPanel up;
    private JPanel down;
 
    public GetGCD() {
  
        super("최대 공약수 구하기");
        setDefaultCloseOperation(EXIT_ON_CLOSE);
        setLayout( new FlowLayout( FlowLayout.LEFT ) );
        setBounds(x, y, width, height);
        setForeground(Color.black);
        setBackground(Color.lightGray);
        setVisible(true);
  
        Container content = getContentPane();
  
        up = new JPanel();
        down = new JPanel();
  
        content.add(up);
        content.add(down);
  
        description = new JLabel("두 정수 입력 : ");
        first = new JTextField(10);
        second = new JTextField(10);
        submit = new JButton("입력");
        area = new JTextArea(11,42);
  
        up.add(description);
        up.add(first);
        up.add(second);
        up.add(submit);
  
        down.add(new JScrollPane(area));
  
        submit.addActionListener(this);
    }
 
    @Override
    public void actionPerformed(ActionEvent arg0) {
        // TODO Auto-generated method stub
        int one = Integer.parseInt(first.getText());
        int two = Integer.parseInt(second.getText());
  
        stringBuffer = new StringBuffer("*** 두 정수의 최대 공약 수 ***\n");
  
        stringBuffer.append("첫번째 정수의 약수 : ");
        getDivisor(one);
        stringBuffer.append("\n두번째 정수의 약수 : ");
        getDivisor(two);
  
        getGreatestCommonDivisor(one, two);
  
        area.setText("");
        area.append( stringBuffer.toString() );
    }
 
    protected void getDivisor(int one){
        for ( int i = 1 ; i <= one ; i++ ) {
            if ( one % i == 0 ) {
                stringBuffer.append( i + "  " );
            }
        }
    }
 
    protected void getGreatestCommonDivisor(int one, int two) {
  
        int greate = 0;
  
        if ( one >= two ) {
            greate = one;
        } else {
            greate = two;
        }
  
        for ( int i = 1 ; i < greate ; i++ ){
            if ( one % i == 0 ) {
                if ( two % i == 0 ){
                    GCD = i;
                }
            }
        }
  
        stringBuffer.append("\n최대 공약수 : " + GCD);
  
    }
 
    public static void main(String[] args) {
        new GetGCD();
    }

 
}

[위 코드의 실행 파일] 

ShowGetGCD.jar

 

ShowGetGCD.jar

0.0MB