1) 약수 - 자연수 N에 대하여 자연수A로 나눴을때 나머지가 0일때, A는 N의 약수라고 정의한다.
2) 최대공약수 - 자연수 N,M의 공통된 약수 중 가장 큰 수를 최대공약수라고 정의한다.
3) 최소공배수 - 자연수 N,M의 공통된 배수 중 가장 작은 수를 최소공배수라고 정의한다. (두 수의 곱을 최대공약수로 나누면 그 값이 최소공배수가 된다.)
public class Practice {
//약수 구하는 메서드
public ArrayList getDivisor(int num) {
//약수를 담을 배열 선언
ArrayList result = new ArrayList();
for (int i = 1; i <= num; i++) {
//i는 1부터 num까지이므로, 나눴을 때, 나머지가 0일 때, result배열에 i를 추가한다
if (num % i == 0) {
result.add(i);
}
}
return result;
}
//최대 공약수
public int getGCD(int numA, int numB) {
//최대 공약수를 담을 변수 선언
int gcd = 1;
//두 수(numA,numB)의 약수를 담을 배열 선언
ArrayList divisorA = new ArrayList();
ArrayList divisorB = new ArrayList();
//두 수의 약수를 구하는 메서드
for (int i = 1; i <= numA; i++) {
if (numA % i == 0) {
divisorA.add(i);
}
}
for (int i = 1; i <= numB; i++) {
if (numB % i == 0) {
divisorB.add(i);
}
}
//두 수의 약수 배열을 돌면서 가장 큰 값을 gcd에 저장
for (int itemA : ArrayList<Integer>divisor) {
for (int itemB : ArrayList<Integer>divisorB) {
//itemA와 itemB가 같다면(두 수의 공약수라면)
if (itemA == itemB) {
//그 수가 gcd보다 크면 그 수를 gcd에 저장한다.
if (itemA > gcd) {
gcd = itemA
}
}
}
}
return gcd;
}
//최소 공배수
public int getLCM(int numA, int numB) {
//최소 공배수를 담을 변수 선언
int lcm = -1;
//최대 공약수를 구하는 메서드 실행
int gcd = this.getGCD(numA, numB);
//최대 공약수를 구하는 메서드에서 정상적으로 최대 공약수가 구해 졌다면 두 수를 곱해서 최대 공약수로 나눠준다(최소공배수)
if (gcd != -1) {
lcm = numA * numB / gcd;
}
return lcm;
}
//제대로 실행 되는지 확인을 위한 메인 클래스 구현
public static void main(String[] args) {
int numA = 4;
int numB = 20;
Practice p = new Practice();
//두 수의 약수를 배열에 집어 넣는다
ArrayList Alist = p.getDivisor(numA);
ArrayList Blist = p.getDivisor(numB);
System.out.println("numA의 약수 : " + Alist);
System.out.println("numB의 약수 : " + Blist);
System.out.println("===구분선===");
System.out.println("numA와 numB의 최대 공약수 : " + p.getGCD(numA,numB));
System.out.println("numA와 numB의 최소 공배수 : " + p.getLCM(numA,numB));
}
}
//결과값
numA의 약수 : [1, 2, 4]
numB의 약수 : [1, 2, 4, 5, 10, 20]
===구분선===
numA와 numB의 최대 공약수 : 4
numA와 numB의 최소 공배수 : 20