챕터4-5. 수학 | 소인수분해, 팩토리얼(Prime Factorization, Factorial)

소인수분해(Prime Factorization)

# 개념
- 어떤 수 N을 소수의 곱으로 표현하는 것
- 소수를 직접 구하지 않아도 되며, 소수인지 아닌지 판단했던 원리를 이용한다.
- n이 소수가 아닌 경우, 1과 n을 제외한 두 수 n = a * b 형태로 나타낼 수 있고
    중복되는 조합을 제외하기 위해 a<=b 라는 조건을 주면, a==b일때가 루트n일 때 이므로 a의 범위는 2 <= a <= 루트n 이다.
    위의 원리로 n이 소수가 아니라면 2~루트n 사이의 숫자 중 하나로 나누어 떨어지게 되어있으므로
    n이 소수가 될 때 까지 2~루트n 사이의 숫자로 나눠준 뒤 마지막에 남은 수는 소수이므로 그냥 출력해주면 된다.

@ 소인수분해를 하는 방법

#include <iostream>

using namespace std;

int main() {
    int n = 6;

    for (int i = 2; i*i <= n; i++)
    {
        while(n%i == 0)
        {
            cout << i << "\n";
            n = n / i;
        }
    }

    
    if (n > 1)
        cout << n << "\n";  //2~루트n으로 나누어 떨어지지 않고 남은 수는 소수이므로 그냥 출력
}

팩토리얼(Factorial)

# 개념
- N! = 1 x 2 x ... x N 으로 매우 큰 값을 가진다.
- 10! = 3,628,800 정도가 풀 수 있는 문제의 규모이다.

위 개념을 적용한 문제풀이

# 소인수분해 문제

- https://www.acmicpc.net/problem/11653

 

# 팩토리얼 결과 출력 문제
- https://www.acmicpc.net/problem/10872

 

# 팩토리얼 결과에서 0의 개수를 구하는 문제
- https://www.acmicpc.net/problem/1676
- 방법2가 더 효율적임

 

@ 방법 1) 소인수분해한 결과에서 5의 개수를 구하는 방법
- 소인수 분해를 한 뒤 2와 5가 모두 존재할 때 각각의 제곱승을 중 작은 제곱승의 개수가 결과에서의 0의 개수가 된다.
- ex) 10! = 2^8 x 3^4 x 5^2 x 7  = (2^2 x 5^2) x 2^6x 3^4 x 7 = (10^2) x 2^6x 3^4 x 7
         즉, 10! 일땐 결과에서의 0의 개수는 2개이다.
- 팩토리얼을 인수분해 했을 때 2의 개수 보다는 5의 개수가 훨씬 적기 때문에 0의 개수는 5의 개수를 따라간다.
- 따라서 각 자리를 소인수 분해한 결과에서 5의 개수만 세어주면 된다.

 

@ 방법2) 팩토리얼을 펼친 것 N * N-1 * ....* 2 * 1 즉, 1~N에서 
            5의 배수가 몇 개인지 + 5^2의 배수가 몇 개인지 + ... 5^n 이 N보다 작을 때 까지. 더해줌.
- ex) 100! = 1 x 2 x 3 x ... x 100 각각의 인자에서 
   5^1 = 5의 배수만 떼어보면 '20개의 인자' 5, 10, 15, 20, 25, ...., 100가 있고,
   => 20개인 것은 N/5 하면 알 수 있음.
   5^2 = 25의 배수만 떼어보면 '4개의 인자가' 25, 50, 75, 100가 있다.(25의 배수는 5로 나눠도 5를 하나씩 더 가지고 있기 때문)
   => 4개인 것은 N/5*5 하면 알 수 있음.
   5^3  = 125 는 N인 100보다 크므로 따지지 않음.
   따라서 1~100에서의 5의배수, 25의 배수의 개수를 더하여 100!의 결과에서 맨 뒤 0의 개수는 24개.

# nCm 결과에서 0의 개수를 구하는 문제
- https://www.acmicpc.net/problem/2004
- nCm = n! / m!(n-m)! 이고 계산 결과는 분모가 분자에게 모두 약분되므로 항상 정수이다. 
- 위의 문제와 다르게 나눗셈이기 때문에 위와 같이 5의 개수만 보고 판단할 수 없다.
   따라서 이 문제에서는 2의 개수와 5의 개수를 동시에 세어주어야 한다.
   분모는 모두 약분되어 없어지기 때문에 
   분자에서 센 2와 5의 개수에서 분모에서 센 2와 5의 개수를 각각 빼주어 2와 5의 개수를 구하자.
- 2와 5의 개수를 구할 때 i*=2, i*=5 때문에 int형의 저장범위를 넘어갈 수 있으므로 long long 형을 사용하자.