정수론 및 조합론

사요·2021년 9월 22일

알튜비튜

목록 보기

5/16

모든 사진 자료에 관한 출처는 아래 알튜비튜 - 튜터링에 있음을 밝힙니다.
https://github.com/Altu-Bitu/Notice

📗 최대공약수

방법 1. 소인수분해 이용
; 구현이 까다로움
방법 2. 두 수 중 작은 수 기준으로 돌리면서 가장 큰 공통 약수 구하기
; 시간복잡도 O(N)

int gcdBad(int a, int b) {

	//두 수 중 더 작은거 기준으로 하나씩 감소하며 공약수 있는지 판단.

	for (int i = min(a, b); i > 1; i--) {


		if (a % 1 == 0 && b % i == 0) {
			return i;
		}
	}
	return 1; // 끝까지 없다면 최대공약수는 1
}

✨방법 3. 유클리드 호제법✨
; 시간복잡도 O(logN)

💡유클리드 호제법 원리

A와 B의 최대공약수 = A%B와 B의 최대공약수

1. 증명

gcd(a, b)=G라 하자.
그럼
A = a • G
B = b • G
(a,b 는 서로소)

A = q • B + r (q= A/B의 몫, r=A%B) 이라고하고

A = a • G , B = b • G 를 대입해보자.

aG=q•bG+r --정리하면--> r=G(a-bq) 라는 식을 얻을 수 있다.

r = G(a-bq)
B = b • G
그럼 B 와 r간에 G라는 공통약수가 생긴다.

우리는 B와 r(A%B)의 최대공약수가 A와 B의 최대공약수인 G와 같다는것을 증명해야하므로 a-bq와 b가 서로소 라는것을 증명해주면 된다.

이를 증명하기 위해서 가정하고 모순을 확인하는 귀류법을 사용하자.

우선, a-bq와 b가 서로소가 아니라고 가정하자. 그렇다면 두수는 공통인 약수(t)를 가져야한다.

a-bq =mt ...(1)
b=nt ... (2)

(2) 식을 (1)에 대입하면

a-ntq=mt ---> `a = t (m+qn)

a=t (m+qn)
b=tn

바로 이때, a,b 의 공통약수 t가 생겨 우리가 a,b를 서로소라고 했던 가정에 모순된다.
따라서 a-bq와 b는 서로소가 맞으므로

A%B(r)과 b의 최대공약수 또한 G라고 할 수 있다.

GCD(A,B) = GCD(B,A%B)

2. 과정

두 정수 a,b가 주어진다. (a>b)
a와 b의 최대공약수는 a%b와 b의 최대공약수와 같다.
a%b를 구한 후 왼쪽값 > 오른쪽 값 이어야 하므로
a%b와 b의 위치를 바꾼다.
b의 값이 0일때 a의 값이 최대공약수이다.

👾 유클리드 호제법 구현

1. 반복문


int main()
{
	int a, b;
    
	cin >> a >> b;


	//GCD (a,b) = GCD (b,a%b)

	while (b) //b가 0일때 a가 최대공약수 
	{

		int tmp = a % b;
		a = b; 
		b = tmp;
		
	}

	cout << a;
    }

2. 재귀함수

int GCD_ucild(int a, int b) {

	if (b == 0) return a; //

	else return  GCD_ucild(b, a % b);

}

🌈 최소공배수

두수의 곱 = 최대공약수(GCD) • 최소공배수(LCM)

따라서 최소공배수 = 두수의 곱 / 최대공약수

✒ 소수판별하기

소수판별
1. 2 ~ N 까지 돌리면서 나눠지는 수가 없는지 판단 , O(N)

✨2. 2~ √ N 까지 돌리면서 나눠지는 수가 없는지 판단, O(√N )

🗨부연설명
에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 합성수 m= a*b 이 있다면 a,b 중 적어도 하나는√n이하이다. 즉 n보다 작은 합성수 m은 √n보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, √n 이하의 수의 배수만 지우면 된다.

쉽게 말하면 8 = 4 • 2 인데 4(√ N 이상의 수)로 나누어 떨어지면 2(√ N 이하의 수)로도 나누어 떨어지기 때문에 특정 숫자가 소수인지 판별하고자할때 굳이 √ N 이상의 수를 확인해줄 필요가 없다는것이다.

그러나 N이 큰 상황에서 한번에 여러개의 소수를 구해야한다면 본 방법으로도 시간이 오래걸릴수 있다. 그럴때 바로 에라토스테네스의 체를 활용할 수 있다!

🥅에라토스테네스의 체

N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘

특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우 유용.
각 수가 소수인지 판단한 여부를 저장하는 배열을 사용.
2~ √n 까지 해당 숫자의 배수에 해당하는 숫자들을 지워나감.
약수가 존재하는 숫자들은 체에 의해 걸러진다.
따라서 걸러지지 않은 숫자들은 소수
O(nlog(logn))만에 2~n 범위의 수들에 대해 소수판정이 가능하다.

과정

1은 소수가 아니므로 그냥 지워준다.
2를 제외한 2의 배수를 지운다.
3을 제외한 3의 배수를 지운다.
5를 제외한 5의 배수를 지운다.
그림의 경우, 우리가 구하고자하는 소수의 범위는 n= 30까지였으므로 2~ √30 (약 5. xx) 까지 검사를 해주면 된다. 즉, 6보다 작은 수의 배수(2, 3, 5)들만 지워도 충분하다. 이와같은 과정을 반복했을때 남아있는 수들이 소수가 된다.

🔬코드 구현

#소수가 맞다면 #true값을 저장하자. #에라토스테네스의 체

//n : 소수를 판별하고자하는 숫자 범위, is_prime :소수 여부를 저장
void isPrime(int n, vector<bool>& is_prime) {

	//0과 1은 소수가 아니니까 먼저 제거
	is_prime[0] = is_prime[1] = false;
	

	//2~ 제곱근 n 까지 검사
	for (int i = 2; i <= sqrt(n); i++) {

		if (is_prime[i]) { //i가 소수라면 
			for (int j = i*i; j <= n; j += i) {

				is_prime[j] = false;

			}
		}

	}

}