소인수분해

소인수분해의 뜻은 임의의 수(소수 또는 합성수)를 소수의 곱으로 표현한 것을 말한다

 

예를 들어 28을 소인수분해하면 2*2*7 이 된다.

 

소인수분해나 소수를 관련하여 문제를 풀 때는

항상 N이라는 수를 p*q 로 나타낼 때

p가 sqrt(N)보다 크거나 같다면 q는 sqrt(N)보다 작거나 같다는 것을 이용해야 한다.

 

소인수분해를 가장 간단히 하는 방법은

N을 기준으로 2부터 sqrt(N)까지 가능한 수를 모두 나누어보는 것이고

이 때의 시간복잡도는 sqrt(N)이 된다

 

만약 폐구간[a,b] 에 대한 범위를 다루어야 한다면,

에라토스테네스의 체를 이용하여 좀 더 쉽게 해결할 수 있다.

에라토스테네스의 체를 구현하되, 소인수분해를 적용하려면 다음과 같다

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
using namespace std;
 
int factor[1001];
 
int solve(int n) {
    if (n <= 1) return 1;
 
    cout << "현재 수는 " << factor[n] << " 입니다\n";
 
    return factor[n] * solve(n / factor[n]);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    // 자기 자신을 소수로 둔다
    for (int i = 0; i < 1001; i++) factor[i] = i;
 
    for (int i = 2; i < sqrt(1001); i++) {
        // 만약 소수이면 (다른 수를 안만났으면)
        if (factor[i] == i) {
            for (int k = i * i; k < 1001; k += i) {
                // 초기화가 안됬을 때만
                if (factor[k] == k) factor[k] = i;
            }
        }
    }
 
    int n; cin >> n;
    cout << solve(n);
 
    return 0;
}

 

factor[i]의 의미는 "i라는 수를 만들기 위해 곱해야할 최소의 수" 를 뜻한다.

factor[2] 는 2가 될 것이고, factor[12] 역시 2가 될 것이고

2의 배수가 아닌 3의 배수만 생각해봐도 factor[9] 는 3이 됨을 뜻한다.

 

32줄의 조건문을 확인해주는 경우는

예를 들어 6을 생각했을 때

2가 먼저 factor[6] 에 담기게 된다.

그 후 3에 대한 반복문을 돌 때 factor[6]을 거치기 때문에 조건처리를 안해주면

factor[6] = 3 으로 수정되면서 6을 만들기 위한 최소곱의 값이 2가 아닌 3이 되기 때문이다.

 

위에서 28이라는 수를 소인수분해하면 2 2 7 이라고 말했었다.

코드가 제대로 구현되었는지 확인해보았다.