나머지 연산
나머지구하기
컴퓨터는 처리할 수 있는 정수의 길이가 제한되어있다. 가끔씩 컴퓨터가 처리할 수 있는 범위를 벗어나는 아주 큰 수를 처리를 해야될 때가 있는데 이럴때 주로 답을 M으로 나눈 나머지를 구하라는 문제가 나온다.
( 정답을 M으로 나눈 나머지를 출력하라 )
- 덧셈 : (X + Y)mod M = ((X mod M) + (Y mod M))mod M
- 곱셈 : (X x Y)mod M = ((X mod M) x (Y mod M))mod M
- 나눗셈인 경우는 성립하지 않음.
- 뺄셈 : (X - Y)mod M = ((X mod M) - (Y mod M) + M)mod M
뺄셈인 경우는 mod한 연산 결과가 음수가 나올 수 있기 때문에 따로 M을 더해주어 연산을 처리한다.
최대공약수
두 수 X와Y의 최대공약수G는 X와Y의 공통된 약수 중에서 가장 큰 정수이다.
최대공약수는 줄여서 GCD라고 한다.
최대공약수를 구하는 두 가지 방법
- 2부터 min(X,Y)까지 모든 정수로 나누는 방법
int g = 1;
int gcd(int x, int y){
for(int i = 2; i<min(x,y); i++){
if(x%i == 0 && y%i == 0)
g = i;
}
}- 유클리드 호제법(Euclidean algorithm)
x와 y를 나눈 나머지를 r이라고 했을 때, gcd(x,y)의 값과 gcd(y,r)의 값이 동일하다는 성질을 이용한다.
이때 r이 0이 될때의 y가 최대공약수가 된다.
// reculsion을 이용한 방법
int gcd(int x, int y){
if(y == 0)
return x;
return gcd(y, x%y);
}
// 반복문을 이용한 방법
int gcd(int x, int y){
while(y != 0){
x = y;
y = x%y;
}
return x;
}*x,y,z의 최대공배수를 구하는 것은 gcd(gcd(x,y),z)를 이용하면 된다.
최소공배수
두 수 X와Y의 최소공배수L은 X와Y의 공통된 약수 중에서 가장 작은 정수이다.
최소공배수는 줄여서 LCM이라고 한다.
최소공배수는 최대공약수를 이용하여 푼다.
정수 A와 B가 있다.
A와 B의 최대공약수를 G라고 하고, 최소공배수를 L이라고 하면 다음과 같은 식이 성립한다.
A x B = G x L위의 식을 이용하여 최소공배수 식을 도출하면 다음과 같다.
LCM(A,B)= (A x B) / GCD(A,B)소수
소수의 정의 : 약수가 1과 자기자신 밖에 없는 수. (1은 소수가 아니다.)
ex) 2,3,5,7 ...
N이 소수가 되려면 2이상 N-1이하의 자연수 중 나누어 떨어지는 자연수가 존재해서는 안된다.
소수와 관련된 알고리즘은 두개가 있다.
- 어떤 수 N이 소수인지 아닌지 판별하는 알고리즘
소수를 판별하는 알고리즘을 작성하는 코드는 여러가지가 있다.
가장 기본적인 방법 - 시간복잡도 O(N)
bool prime(int N){
if( N < 2 )
return false;
for(int i=2; i<N; i++){
if(N%i == 0)
return false;
}
return true;
}
두 번째 방법 - 시간복잡도 O(2/N)
N이 소수가 되려면 2이상 N/2이하의 자연수 중 나누어 떨어지면 안된다.
위와같은 경우가 성립되는 이유는 N의 약수 중에서 가장 큰 것은 N/2보다 같거나 작기 때문이다.
N이 axb로 나타낼 수 있다고 했을 때, a는 작을수록 b는 커진다.
가능한 a중 가장 작은 값은 2이고, 그렇게 되면 b는 N/2를 넘지 않는다. bool prime(int N){
if( N < 2 )
return false;
for(int i=2; i<N; i++){
if(N%i == 0)
return false;
}
return true;
}
세 번째 방법 - 시간복잡도 O(√N)
N이 소수가 되려면 2이상 √N이하의 자연수 중 나누어 떨어지면 안된다.
N을 axb로 표현할때, 두 수 a와b의 차이가 가장 작은 경우는 √N이다.
N = axb
만약 a < √N 이고, b < √N 이면 axb < N이 되기 때문에 안된다.
만약 a > √N 이고, b > √N 이면 axb > N이 되기 때문에 안된다.
따라서 a ≤ √N 이고, b ≥ √N 이다. //i<루트N 은 i*i<N과 같다.
bool prime(int N){
if( N < 2 )
return false;
for(int i=2; i*i<N; i++){
if(N%i == 0)
return false;
}
return true;
}
- N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 알고리즘
위의 알고리즘일 경우는 첫번째 방법을 사용하면 너무 긴 시간을 필요한다. 따라서 이와 같은 경우는 에라토스테네스의 체를 이용한다.
에라토스테네스의 체
1. 2부터 N까지의 수를 써 놓는다.
2. 지워지지 않은 수 중 가장 작은 수를 찾는다. (찾은 수는 소수이다.)
3. 찾은 수의 배수를 찾아 모두 지운다.
4. 지워지지 않는 수의 제곱이 N을 넘기지 않을 때까지 2~3의 과정을 반복한다.
EX) 100이하의 수 중 소수를 모두 찾아라.
-
2부터 N까지의 수를 써 놓는다.
-
지워지지 않는 수 중 가장 작은 수는 2이므로 2의 배수를 찾아 지운다.
-
지워지지 않는 수 중 2 다음으로 작은 수는 3이므로 3의 배수를 찾아 지운다.
-
지워지지 않는 수 중 다음으로 작은 수는 5이므로 5의 배수를 찾아 지운다.
-
지워지지 않는 수 중 다음으로 작은 수는 7이므로 7의 배수를 찾아 지운다.
-
지워지지 않는 수 중 다음으로 작은 수는 11인데 11의 제곱은 121로 100을 넘기므로 지우는 과정은 끝이나고 아래의 표에 있는 수가 답이 된다.
CODE
int prime[100]; //소수 저장
int pcount = 0; // 소수 count
bool check[101]; //지워졌으면 true
int N = 100;
for (int i=2; i<=N; i++) {
if (check[i] == false) {
prime[pn++] = i;
// for(int j=i*2; j<=N; j+=i){
for (int j = i*i; j<=N; j+=i) {
check[j] = true;
}
}
}
골드바흐의 추측
골드바흐의 추측이란 2보다 큰 모든 짝수는 두 소수의 합으로 표현가능하다는 가설이다. 이 가설은 아직 증명이 되지는 않았지만 10의 18제곱 이하에서는 참인 것이 증명이 되었다.
골드바흐의 약추측이라는 것도 존재하는데 이는 5보다 큰 홀수는 세 소수의 합으로 표현가능하다는 추측인데 이것은 골드바흐의 추측에 3을 더한 것이다.
N이라는 짝수가 존재한다.
N이 a+b로 구성되어 있다 할때, b가 소수라면 N-b가 소수이어야 한다.
이는 에라토스테네스의 체 알고리즘을 이용하면된다.
a가 에라토스테네스에서 구한 소수를 모두 순회하는 수라고 가정하면, 우리는 N-b가 소수인지 아닌지만 검사하면 된다.
즉, check[N-b]가 false인지 확인하면 된다.
참고
모든 소수는 6으로 나눈 나머지가 1 or 5이다.
따라서 모든 소수는 6n+1 또는 6n+5로 표현할 수 있다.
팩토리얼
