[C++/코테] 수학

소수

• 1과 자기 자신으로만나누어지는 수. ↔ 합성수
  1은 소수도 합성수도 아니다!
• 약수가 2개인 수
• 2부터 N-1까지의 수로 나누어지지 않는 수 → 시간 복잡도가 $O(N)$

1. 소수 판정법 

합성수 N에서 1을 제외한 가장 작은 약수는 ${\sqrt N}$

 ex) N = 18 → 2 ≤ $\sqrt 18$

 ex) N = 25 → 5 ≤ $\sqrt 25$

 ex) N = 21 → 3 ≤ $\sqrt 21$

즉, 2부터 $\sqrt N$까지의 수로 나누어지지 않으면 소수임을 알 수 있음. 시간 복잡도 $O(\sqrt N)$ 소요

bool isprime(int n){
    if(n == 1) return 0;
    for (intn i = 2; i*i < n; i++){
        if(n % i == 0) return 0;
    }
    return 1;
}

실수의 저장/연산 과정에서의 오차 때문에 sqrt 함수를 사용할 수 없다. 대신 조건문에 i * i 를 해준다.

 

연습문제

백준 1978: 소수 찾기 https://www.acmicpc.net/problem/1978

 

2. 범위 내에서의 소수 판정법

(1) 범위 내의 각각 숫자들이 소수인지 판정

vector<int> primelist(int n){
    vector<int> primes;
    for (int i = 2; i <= n; i++){
        bool isprime = 1;
        for (int j = 2; j*j <= i; j++){
            if(i % j == 0){
                isprime = 0;
                break;
            }
        }
        if (isprime) primes.push_back(i);
    }   
    return primes;
}

# 개선 ver. 2부터 루트 N까지의 범위에서만 나눠준다.
vector<int> primelist(int n){
    vector<int> primes;
    for (int i = 2; i <= n; i++){
        bool isprime = 1;
        for (int p: primes){
            if(p*p > i) break;
            if (i % p == 0){
                isprime = 0;
                break;
            }
        }
        if (isprime) primes.push_back(i);
    }   
    return primes;
}

(2) 에라토스테네스의 체

k를 제외한 k의 배수들을 모두 거르며 (False로 만든다.) 합성수를 제거해 나가는 방법

vector<int> sieve(int n){
    vector<int> primes;
    vector<bool> state(n+1, true);
    state[1] = false;		// 1은 소수가 아니다.
    for (int i = 2; i <= n; i++){
        if(!state[i]) continue;
        for (int j = i*i; j <= n; j += i){
            state[j] = false;
        }
    }
    for (int i =2; i <= n ; i++){
        if (state[i]) primes.push_back(i);
    }
    return primes;
}

배열이 아닌 vector로 두면 저장 공간을 8배 정도 절약하는 최적화 코드를 짤 수 있다.

 

연습문제

백준 1929: 소수 구하기 https://www.acmicpc.net/problem/1929

 

3. 소인수분해

• 정수를 소수의 곱으로 나타내는 것
• 모든 자연수는 소인수분해하는 방법이 하나뿐이다. 

연습문제 _소인수분해 구현

백준 11653: 소인수분해 https://www.acmicpc.net/problem/11653

#include <bits/stdc++.h>
using namespace std;

int main(void){
    ios::sync_with_stdio(0);
    sin.tie(0);
    int n;
    cin >> n;
   
    for (int i = 2; i*i <= n; i++){
        while(n%i == 0){
            cout << i << '\n';
            n \= i;
        }
    }
    if (n != 1) cout << n;
}

• 에라토스테네스의 체를 사용한다. 
  i = 2부터 시작하여 주어진 수 (N)을 반복적으로 나눈다. 나누어 떨어지지 않으면 i를 1 증가시키고, 나누기를 반복.
• N이 전부 나누어떨어져서 1이 될 때 종료 → $O(N)$ 시간복잡도
  i * i > N 일 때 종료 → $O(\sqrt N)$ 시간복잡도 (* 상단 소수판정법 참고)

최대공약수

• 약수: 어떤 수를 나누어 떨어지게 하는 수

vector<int> divisor(int n){
    vector<int> div;
    for (int i = 1; i*i <= n; i++){
        if(n%i == 0) div.push_back(i);
    }
    for (int j = (int)div.size() - 1; j >= 0; j--){   // div.size() - 1 : 약수 목록을 크기 순으로 저장하기 위해
        if(div[j] * div[j] == n) continue;
            div.push_back(n / div[j]);
    }
    return div;
}

• 최대공약수(GCD): 두 자연수의 공통된 약수 중 가장 큰 약수
• 유클리드 호제법 - 두 수 A, B에 대해서 A를 B로 나눈 나머지를 r이라고 하면 GCD(A, B) = GCD(B, r)이다.
  ex) GCD(20, 12) = GCD (12, 8) = GCD(8, 4) = GCD(4, 0) = 4

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

• 최소공배수(LCM): A $\times$ B = GCD(A, B) $\times$ LCM(A, B)

int lcm(int a, int b){
    return a/ gcd(a, b) * b;	// a* b/gcd(a,b) 가 아닌 이유 int overflow 방지
}

연립합동방정식

연습문제

백준 6064 카잉달력 https://www.acmicpc.net/problem/6064

이항계수

색이 다른 공 n개중에서 k개를 선택,

순열 - 순서를 고려한 뽑기 $_nP_k$

조합 - 순서를 고려하지 않은 뽑기  $_nC_k$

 

 

연습문제

백준 11050: 이항계수1 https://www.acmicpc.net/problem/11050

백준 11051: 이항계수2 https://www.acmicpc.net/problem/11051

• $_nC_k = n- _1Ck + n - _1C_k - 1$ 라는 조합의 성질이 자주 쓰인다. DP로 구현 가능하다.

 

---

출처:

https://blog.encrypted.gg/983

[실전 알고리즘] 0x12강 - 수학