정수론과 조합론

eee·2025년 3월 19일

정수론 조합론

알고리즘

목록 보기

3/9

정수론

유클리드 호제법

2개의 자연수의 최대공약수를 구하는 알고리즘
a를 b로 나눈 나머지를 r이라 하면,
a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질 이용

// 재귀
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 반복문
int gcd_iter(int a, int b) {
    while (b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

에라토스테네스의 체

https://www.acmicpc.net/problem/2960

1부터 N까지의 모든 소수를 빠르게 구하는 알고리즘
N 이하의 모든 자연수에서 소수의 배수를 제거하는 방식

vector<bool> isPrime(N, true);
isPrime[0] = isPrime[1] = false;

for (int i = 2; i * i <= N; i++) {
		if (isPrime[i]) {
			for (int j = i * i; j <= N; j += i) 
				isPrime[j] = false;
		}
}