최대공약수와 최소공배수 (+ 소수)

1. 최대공약수 (Greatest Common Divisor)

- 나눈 값이 0보다 클때까지 반복 (유클리드 호제법 사용)

- 알고리즘 예시 : 

public static int gcd(int a, int b) {
	if(b == 0) return a;
	else {
		int tmp = b;
		b = a % b;
		a = tmp;
		
		return gcd(a, b);
	}
}

 

2. 최소공배수 (Least Common Multiple)

- 최대공약수와의 관계를 이용해서 구함

- 알고리즘 예시 : 

public static int lcm(int a, int b) {
	return ((a * b) / gcd(a, b));
}

 

3. 소수 (Prime Number)

- "1과 그수 자신 이외의  자연수로는 나눌 수 없는, 1보다 큰자연수이다." (https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98)

- 알고리즘 예시 : 

public static boolean isPrime(int n) {
	if(n == 1) return false;
	else {
		for(int i = 2; i < n; i++) {
			if(n % i == 0) return false;
		}
		
		return true;
	}
}

- 시간초과가 날 경우가 있기 때문에 "에라토스네테스의 체" 사용하기 (https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4)