[C++][알고리즘] 소인수분해

소인수분해란?

소인수분해는 말 그대로 어떤 수를 소수들의 곱으로 나타내는 것을 의미합니다.

예를 들어 12를 소인수분해하면 2 x 2 x 3로 나타낼 수 있습니다.

7과 같은 소수는 분해하면 자기 자신인 7만 남게 됩니다.

이렇게 나타내면 원래 수를 더 작은 소수들의 곱으로 표현하는 것이 가능해집니다.

 

소인수분해 예시코드1

#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;

    for (int i = 2; i * i <= N; ++i) {
        while (N % i == 0) {
            cout << i << endl;
            N /= i;
        }
    }

    if (N > 1) {
        cout << N << endl;
    }

    return 0;
}

 

소인수분해 예시코드2

#include<iostream>

using namespace std;

int main() 
{
	int N;

	cin >> N;

	for (int i = 2;N>1;)
	{
		if (N % i == 0)
		{
			cout << i << endl;
			N /= i;
		}
		else
		{
			i++;
		}
	}
	return 0;
}

 

대략적으로 두 가지 방법이 있지만 첫 번째 코드가 더 효율적이고 가독성이 좋은 것 같습니다.