C++ 알고리즘 나머지 연산/최대공약수/소수

(A+B) mod M  = ((A mod M) + (B mod M)) mod M

(A*B) mod M = ((A mod M) * (B mod M)) mod M

뺄셈의 경우에는 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 해야 한다.

(A-B) mod M = ((A mod M) - (B mod M) + M) mod M

 

최대공약수(GCD)는 유클리드 호제법을 이용하는 방법이 제일 좋다.

유클리드 호제법 : a를 b로 나눈 나머지를 r이라고 했을 때

GCD(a, b) == GCD(b, r)

그래서 r==0 일 때의 b값이 최대공약수이다.

 

재귀 함수를 사용해서 유클리드 호제법을 구현해보자!!

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

재귀 함수를 사용하지 않고 구현해보면

int gcd(int a, int b) {
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

최소공배수(LCM)는 최대공약수를 이용해서 구할 수 있다.

G = GCD(A, B)라고 하면

A*B = GCD(A, B) * LCD(A, B)이다.

따라서 LCM(A, B) = A*B/G로 구할 수 있다!!

 

이제 제일 중요한 소수이다.

소수와 관련된 알고리즘은 두 가지가 있다.

1. 어떤 수 N이 소수인지 아닌지 판별하는 방법

2. N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법

 

소수는 약수가 1과 자기 자신밖에 없는 수이다.

N이 소수가 되려면 2보다 크거나 같고 N-1보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.

그래서 이 성질을 이용해 코드를 짜 보면

bool prime(int n) {
	if (n < 2) {
    	return false;
    }
    for (int i = 2; i <= n - 1; i++) {
    	if (n % i == 0) {
        	return false;
        }
    }
    return true;
}
    

이러면 n을 2부터 n-1까지 다 일일이 나눠서 소수인지 아닌지 판단하기 때문에 시간 복잡도는 O(n)이다.

그런데 i가 n/2보다 크다면 어차피 이 수는 n을 나누지 못한다.

그래서 우리는 4번째 줄 for문 안의 i <= n-1을 i <=n/2로 바꿔도 식이 성립하는 것을 알 수 있다.

이렇게 해도 시간 복잡도는 O(n/2) == O(n)이다.

 

이거보다 더 빠르게 계산할 수 있는 방법은 i <=루트 n 까지만 검사해 보는 것이다!!

루트 n까지만 검사하면 되는 이유를 간단히 생각해보자!!

n이 합성 수라면 1과 n 말고 다른 인자들을 가질 것이다. 

그러면 n = a*b로 나타낼 수 있는데 (a == b인 경우는 둘 다 루트 n이고 어차피 소수 아님)

a> 루트 n이고 b> 루트 n 이면 a*b> n 이기 때문에 모순이고

a <루트 n이고 b <루트 n 이면 a*b <n 이기 때문에 모순이다.

따라서 a, b 둘 중에 하나는 무조건 루트 n보다 작을 수밖에 없어서 루트 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;
}

이 경우 시간 복잡도는 O(sqrt(n))이라 위의 방법들보다 훨씬 빠르다!!

 

그런데 이 방법을 사용해 1부터 N까지의 모든 소수를 구하는데 걸리는 시간은 O(Nsqrt(N))으로 너무 긴 시간이 걸린다.

그래서 1부터 N까지의 모든 소수를 구할때는 에라토스테네스의 체 방법을 사용한다.

 

이건 다음 게시글로 써야겠다!!!