정수론 관련 주요 알고리즘을 어딘가에 기록해두면 좋을 거 같아서, 코드 위주로 한번 모아봤다. (알고리즘에 대한 설명은 거의 없음)
1. 최대공약수 (GCD, Greatest Common Divisor)
(1) 유클리드 호제법 이용
using ll = long long;
ll get_gcd(ll a, ll b) {
while (b != 0) {
ll r = a % b;
a = b;
b = r;
}
return a;
}
- 관련 게시글 (유클리드 호제법) : https://infikei.tistory.com/46
2. 최소공배수 (LCM, Largest Common Multiple)
(1) 최대공약수 이용
$a \times b = \operatorname{GCD}(a, b) \times \operatorname{LCM}(a, b)$이 성립한다는 사실을 이용하여 구할 수 있다.
혹시 모를 오버플로우를 방지하기 위해 나눗셈을 먼저, 곱셈을 나중에 수행해주었다.
using ll = long long;
ll get_lcm(ll a, ll b) {
return a / get_gcd(a, b) * b;
}
3. 소수 판정 (Primality Test)
(1) 기본 코드
하나의 수에 대해 소수 판정을 해야 할 때 주로 사용하는 방법이다.
using ll = long long;
bool is_prime(ll n) {
if (n <= 1) return false;
for (ll i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
또는 sqrt 를 사용할 수도 있지만, 별로 추천하지는 않는다. 실수 연산은 오차가 발생할 수 있기 때문이다. 다만 sqrt(n) 를 미리 구해놓고 시작하면 반복마다 곱하기 연산 1회가 감소하게 된다는 약간의 이득은 있다.
경험상 C++에서는 sqrt 연산 결과를 즉시 정수 자료형으로 변환한다면 큰 문제는 없었다. 다른 언어나 환경에서는 실수 오차에 따라 결과가 잘못될 수 있음에 항상 유의해야 한다.
using ll = long long;
bool is_prime(ll n) {
if (n <= 1) return false;
ll sqrt_n = sqrt(n);
for (ll i = 2; i <= sqrt_n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
(2) $\sqrt{n}$ 이하의 모든 소수들을 이용한 최적화
$\sqrt{n}$ 이하의 모든 소수들(primes)을 구해놓았다는 가정이 필요하다. (후술할 에라토스테네스의 체를 이용하여 구할 수 있음)
using ll = long long;
vector<int> primes; // 이미 구해놓았다고 가정
bool is_prime(ll n) {
if (n <= 1) return false;
for (int i = 0; i < size(primes) && (ll) primes[i] * primes[i] <= n; i++) {
if (n % primes[i] == 0) {
return false;
}
}
return true;
}
4. 에라토스테네스의 체 (Sieve of Eratosthenes)
(1) 기본 코드
$n$ 이하의 모든 수에 대해 소수 판정을 해야 하는 경우, 에라토스테네스의 체를 이용하여 한번에 구할 수 있다.
const int MAX = 1000000;
bool sieve[MAX];
void create_sieve() {
memset(sieve, true, sizeof sieve);
for (int i = 2; i * i < MAX; i++) {
if (sieve[i]) {
for (int j = i * i; j < MAX; j += i) {
sieve[j] = false;
}
}
}
}
(2) $n$ 이하의 모든 소수들을 구해야 하는 경우
$n$ 이하의 모든 소수들을 primes 에 저장한다.
const int MAX = 1000000;
bool sieve[MAX];
vector<int> primes;
void create_sieve() {
memset(sieve, true, sizeof sieve);
for (int i = 2; i * i < MAX; i++) {
if (sieve[i]) {
primes.push_back(i);
for (int j = i * i; j < MAX; j += i) {
sieve[j] = false;
}
}
}
for (int i = primes.back() + 1; i < MAX; i++) {
if (sieve[i]) {
primes.push_back(i);
}
}
}
5. 소인수분해 (Prime Factorization)
(1) 기본 코드
using ll = long long;
vector<ll> get_prime_factorization(ll n) {
vector<ll> ret;
for (ll i = 2; i * i <= n; i++) {
while (n % i == 0) {
ret.push_back(i);
n /= i;
}
}
if (n > 1) {
ret.push_back(n);
}
return ret;
}
(2) 소인수와 지수를 함께 구하는 코드
using ll = long long;
using pll = pair<ll, ll>;
vector<pll> get_prime_factorization(ll n) {
vector<pll> ret;
for (ll i = 2; i * i <= n; i++) {
ll cnt = 0;
while (n % i == 0) {
cnt++;
n /= i;
}
if (cnt >= 1) {
ret.emplace_back(i, cnt);
}
}
if (n > 1) {
ret.emplace_back(n, 1);
}
return ret;
}
(3) $\sqrt{n}$ 이하의 모든 소수들을 이용한 최적화
$\sqrt{n}$ 이하의 모든 소수들(primes)을 구해놓았다는 가정이 필요하다. (에라토스테네스의 체를 이용하여 구할 수 있음)
기본 코드 최적화
using ll = long long;
vector<int> primes; // 이미 구해놓았다고 가정
vector<ll> get_prime_factorization(ll n) {
vector<ll> ret;
for (int i = 0; i < size(primes) && (ll) primes[i] * primes[i] <= n; i++) {
ll p = primes[i];
while (n % p == 0) {
ret.push_back(p);
n /= p;
}
}
if (n > 1) {
ret.push_back(n);
}
return ret;
}
소인수와 지수를 함께 구하는 코드 최적화
using ll = long long;
using pll = pair<ll, ll>;
vector<int> primes; // 이미 구해놓았다고 가정
vector<pll> get_prime_factorization(ll n) {
vector<pll> ret;
for (int i = 0; i < size(primes) && (ll) primes[i] * primes[i] <= n; i++) {
ll p = primes[i];
ll cnt = 0;
while (n % p == 0) {
cnt++;
n /= p;
}
if (cnt >= 1) {
ret.emplace_back(p, cnt);
}
}
if (n > 1) {
ret.emplace_back(n, 1);
}
return ret;
}
6. $n!$에 곱해진 소수 $p$의 개수
(1) 기본 코드
using ll = long long;
ll count_prime_in_factorial(ll n, ll p) {
ll cnt = 0;
for (ll i = p; i <= n; i *= p) {
cnt += n / i;
}
return cnt;
}
(2) 오버플로우 방지
위의 코드에서 i *= p 를 수행할 때 오버플로우가 발생할 가능성이 있다.
오버플로우 방지를 위해서 곱셈을 나눗셈으로 바꾼 버전이다.
using ll = long long;
ll count_prime_in_factorial(ll n, ll p) {
ll cnt = 0;
while (n > 0) {
n /= p;
cnt += n;
}
return cnt;
}
(3) 소수가 아니라 합성수라면?
$n!$에 곱해진 합성수 $k$의 개수를 구해야 할 수도 있다.
우선 $k$를 소인수분해해서 $k$를 이루는 모든 소인수와 그 지수를 알아내야 한다.
이렇게 알아낸 소인수와 지수를 $p_i$, $r_i$라고 하자. 그러면 $k = p_1^{r_1} \times \cdots \times p_m^{r_m}$ 라고 표현할 수 있다.
이제 각각의 $p_i$마다 $n!$에 곱해진 소수 $p_i$의 개수 $a_i$를 구하고, $\left\lfloor \frac{a_i}{r_i} \right\rfloor$ 값을 구한다.
이렇게 구한 값들 중에서 최솟값이 답이 된다.
'Algorithm' 카테고리의 다른 글
| 최대 유량 문제 2편 : 디닉 알고리즘, 최대 유량 최소 컷 정리 (0) | 2025.11.16 |
|---|---|
| 최대 유량 문제 1편 : 포드-풀커슨 알고리즘, 에드몬드-카프 알고리즘 (0) | 2025.11.09 |
| 펜윅 트리 (0) | 2025.10.28 |
| 2025 카카오 공채 1차 코딩테스트 후기 (1) | 2025.10.12 |
| 유클리드 호제법 (0) | 2025.02.13 |