알고리즘 기본기 다지기8.기초 수학 문제풀기 (약수, 배수, 소수)
약수(Divisor)
약수 또는 인수(factor)는 어떤 수로 정수가 나누어 떨어지는 것에 대하여 일컫는 말이다. 대표적으로 1, -1은 모든 수의 약수이다. 0은 자기 자신 외에는 약수가 없다.
배수는 무수히 많이 있지만, 약수의 개수는 항상 유한하다.
최대공약수(GCD, Greatest Common Divisor)
정수들의 공약수(Common factor)는 동시에 해당 정수들이 모두 갖고 있는 약수를 말한다. 적어도 하나가 0이 아닌 정수들의 최대 공약수는 공약수 가운데 가장 큰 하나를 말한다.
- 가장 큰 공약수
- 공약수이자, 모든 공약수의 배수인 양의 정수
- 정수 계수 선형 결합인 최소 양의 정수
- 최대공약수가 1인 정수들을 서로소라고 한다.
최대공약수를 구하는데에는 소인수분해, 유클리드 호제법 등을 사용한다.
가장 빠른 방법은 유클리드 호제법이다
- 정수 a, b의 최대 공약수를 구하고자 한다.(a > b)
- a / b를 진행하여 나머지 c를 구한다.
- b / c 를 진행하여 나머지 d를 구한다.
- 나머지가 0이 될때까지 위 연산을 반복한다.
- 나머지가 0이 나오도록 연산이 나오는 나머지가 두 수의 최대공약수가 된다.
배수(Multiple)
배수는 어떤 선택한 수 n 에 다른 정수를 곱한 수이다. 다로말해 n으로 나누어 떨어지는 수를 일컫는다. 모든 자연수의 배수는 끝이 없기 때문에 배수는 무한이 이루어진다.
최소공배수(LCM, Least Common Multiple)
정수의 공배수는 정의한 모든 수의 배수가 되는 정수이다. 그 중 최소공배수는 양의 공배수 중 가장 작은 하나이다.
최소공배수는 소인수분해를 이용하여 구할 수 있다.
소인수 분해 결과의 약수들 중에서 지수가 가장 큰 수를 찾아 서로 곱한다. 그 값이 최소공배수가 된다.
- 최소공배수 = 정수 a * 정수 b * 정수 c * ... * 정수 b / 최대공약수
소수(Prime Number)
소수는 1보다 큰 자연수 중 자기 자신만을 약수로 가지는 수이다. 소수의 개수는 무한하며, 이는 유클리드 정리에 의하여 최초로 논증되었다. 소수와 그 외의 수를 구분해낼 수 있는 명확한 공식은 아직 밝혀지지 않은 상태이다. 이러한 소수의 성질을 사용하여 암호학에서 많이 사용되고있다.
소인수분해
모든 자연수는 소수의 곱으로 표현될 수 있다. 자연수를 소수의 곱으로 표현될 수 있을 때까지 분해하는 것을 소인수 분해라고 한다.
유클리드의 정리
"소수는 무한하다."
이 명제를 유클리드 정리라고 한다.
유클리드의 정리를 증명하기 위해 많은 증명들이 발표되었다.
- 에우클레이데스의 증명, 골트바흐의 증명, 오일러의 증명, 퓌르스텐베르크의 증명 등
소수 찾기
현재까지 알려진 가장 간단한 방법으로 에라토스테네스의 체가 있다.
찾고자 하는 범위의 자연수를 나열한다
- 2부터 시작하여, 2의 배수를 지워나간다.
- 다음 소수의 배수를 모두 지운다.
- 이를 반복하면 마지막에 남는 수들이 소수이다.
소수를 골라내기 위한 또 다른 방법은 아래와 같다.
- 2와 5를 제외하면 모든 소수의 일의 자리 수는 1,3,7,9,이다.
- 어떤 자연수 n이 소수임을 판정하기 위해서는 루트 n 까지의 수 중 1을 제외하고 그 자연수의약수가 있는지 확인하면 된다.
- 배수의 성질을 이용하면 쉽게 구할 수도 있다.
연습문제
약수 관련 문제들을 풀어보자
백준, Leetcode 기준으로 선별하였으며, 볼드 처리된 문제는 아직 풀지 못했다.
백준 (22 문제)
1978(소수찾기) 1929(소수 구하기) 2609(최대공약수와 최소공배수), 2581(소수), 1934(최소공배수), 11653(소인수분해), 4948(베르트랑 공준=소수찾기) 9020(골드바흐의 추측=소수찾기), 1037(약수), 6588(골드바흐의 추측=소수찾기), 2960(에라토스테네스의 체 = 소수찾기), 9613(GCD 합), 1644(소수의 연속합), 1963(소수 경로), 1850(최대공약수), 1016(제곱ㄴㄴ수=배수), 1850,(최대공약수), 9506(약수들의 합), 13241(최소공배수), 2153(소수단어), 11689(GCD(n,k)=1), 11502(세 개의 소수 문제)
LeetCode (6문제)
264(Ugly Number II) 204(Count Prime) 263(Ugly Number) 1201(Ugly Number III) 313(Super Ugly number) 279(Perfect Squares)
참고
백준 온라인저지 https://www.acmicpc.net/
LeetCode https://leetcode.com/
위키백과(소수) https://ko.wikipedia.org/