Hayden's Archive
[알고리즘] 수학 - 나머지 연산 / 최대공약수 / 최소공배수 / 소수 / 소인수분해 및 팩토리얼 본문
* 나머지 연산(Modular Arthimetic)
- 컴퓨터의 정수는 저장 범위가 한정적 -> 그래서 답을 M으로 나눈 결과를 출력하라는 문제가 종종 나옴
- (A+B)%C 와 (A%C+B%C)%C 는 같고, (A*B)%C 와 (A%C*B %C)%C 는 같다
* 최대공약수(Greatest Common Drivisor = GCD) // 관련 알고리즘 : https://hayden-archive.tistory.com/279
- 서로소(Coprime) : 최대공약수가 1인 두 수
- 최대공약수를 구하는 가장 빠른 방법 -> 유클리드 호제법(Euclidean algorithm) 이용
- 유클리드 호제법 : a를 b로 나눈 나머지를 r이라고 할 때 GCD(a,b) = GCD(b,r)
- 이 때 r이 0이면 그 때 b가 최대공약수
- 예) GCD(24, 16) = GCD(16, 8) = GCD(8, 0) = 8
- 세 수의 최대공약수 구하기 -> GCD(a, b, c) = GCD(GCD(a, b), c)
- 네 수, N개의 숫자도 위와 같이 구할 수 있음
* 최소공배수(Least Common Multiple = LCM)
- 최소공배수는 최대공약수를 응용해서 구할 수 있음
- 두 수 a, b의 최대공약수를 g라고 할 때 최소공배수 l = g * (a/g) * (b/g) 이다.
* 소수(Prime Number) // 관련 알고리즘 : https://hayden-archive.tistory.com/280
- 소수 : 약수가 1과 자기 자신 밖에 없는 수
* 소수와 관련된 알고리즘 2가지
1) 어떤 수 N이 소수인지 아닌지 판별
- N이 소수가 되려면 2보다 크거나 같고, root N보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.
2) N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법
- 에라토스테네스의 체 ( 관련 포스팅 : https://hayden-archive.tistory.com/179 )
| 1. 2부터 N까지 모든 수를 써놓는다. 2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다. 3. 그 수는 소수이다. 4. 이제 그 수의 배수를 모두 지운다. |
| 예) 100 이하의 소수 찾기 STEP 1. 지워지지 않은 수 중에서 가장 작은 수는 2이고, 2는 소수이다. 2의 배수를 모두 지운다. STEP 2. 지워지지 않은 수 중에서 가장 작은 수는 3이고, 3은 소수이다. 3의 배수를 모두 지운다. STEP 3. 지워지지 않은 수 중에서 가장 작은 수는 5이고, 5는 소수이다. 5의 배수를 모두 지운다. STEP 4. 지워지지 않은 수 중에서 가장 작은 수는 7이고, 7은 소수이다. 7의 배수를 지운다. STEP 5. 11의 배수는 이미 지워져 있다. 11×11은 121로 100을 넘는다. 남아있는 모든 수가 소수이다. |
| <실제 코드를 짤 때> * 주의 boolean 타입의 check 배열에 소수가 아닌 숫자 인덱스들에 true 값을 주려고 할 때, 일단 먼저 0과 1은 소수가 아니므로 check[0] = check[1] = true; 로 초기화하고 간다. * 이중 for문 1) i = 2부터 N까지 2) j = i * i부터 N까지(N의 크기가 작을 때) // j = i * 2부터 N까지(N의 크기가 클 때) - i*2부터 i*(i-1)까지는 항상 지워져 있음. (왜냐하면 2의 배수, 3의 배수, 4의 배수, ... 순차적으로 지우기 때문.) (예컨대 i가 7이라면 앞에서 2*7, 3*7, 4*7, 5*7, 6*7은 이미 지웠으므로 7*7부터 시작하면 됨) - 그런데 N의 크기에 따라 N이 너무 크다면 j = i * 2부터 시작한다. (왜냐하면 i가 백만인 경우 i*i는 범위를 넘어간다.) |
| 모든 소수는 6n+1, 6n+5의 형태이다. 따라서 모든 소수는 6으로 나눴을 때 나머지가 1이거나 5이다. 왜냐하면 6n은 2의 배수 6n+1은 소수 6n+2는 2의 배수 6n+3은 3의 배수 6n+4는 4의 배수 6n+5는 소수 -> 이 방법을 쓰면 더 빠르게 풀 수 있지만 에라토스테네스의 체가 워낙 빨라서 실제로는 크게 차이가 나지 않음. |
3) 골드바흐의 추측(Goldbach's conjecture)
- 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.
- 위의 문장에 3을 더하면,
5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다.
- 10^18 이하에서는 참.
소인수분해(PrimeFactorization) 및 팩토리얼(Factorial) 관련 알고리즘 : https://hayden-archive.tistory.com/281
- 팩토리얼은 브루트 포스 할 때 매우 중요.
