-
최대공약수와 최소공배수 (+ 소수)Algorithm\자료구조 2021. 9. 4. 09:37
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)
'Algorithm\자료구조' 카테고리의 다른 글
팩토리얼 / 순열 / 조합 (0) 2021.09.06 그래프의 이해와 종료 (+추가 예정) (0) 2021.08.23 너비 우선 탐색 (Breadth First Search, BFS) (1) 2021.08.23 [알고리즘/Algorithm] 알고리즘의 개요 (0) 2021.08.23