소인수분해

모든 수는 소수의 곱으로 이루어져 있다.

그래서 어떠한 수를 소수들의 곱으로 분해하는 것을 소인수분해라 한다.

72 = 8 * 9 = 2^3 * 3^2, 소수인 2와 3의 곱으로만 이루어져 있다.

void prime_factorization(int a)
{
	//
    int div = 2;
    while (a % div == 0)
    {
    	//
        a /= div;
        cout << div << " ";
    }
    
    for (int div = 3; a > 1; div += 2)
    {
    	//
        while (a % div == 0)
        {
        	//
            a /= div;
            cout << div << " ";
        }
    }
}

나누는 수는 2부터 시작한다. 이는 일반적으로 소수는 홀수인 데, 짝수 중 유일하게 소수인 수가 2이기 때문이다.

그래서 special case인 2는 따로 처리하게 된다.

 

그래서 2가 더 이상 없다면 나누는 수를 3 부터 진행하는데 짝수는 건너뛰면서 반복문을 진행한다. 짝수는 2의 배수이기 때문에, 앞선 반복문에서 체크가 되었기 때문이다.