소인수 분해

• 인수: 어떤 수나 식을 곱하기로 표현했을 때 곱해지는 수

• 소수: 인수가 1과 자신이 전부인 수

• 소인수: 한 수의 인수 중 소수인 것의 집합

vector<int> soin(int n)
{
    vector<int> a;
    
    if(n > 10)
    {
        for(int i = 2; i < n; i++)
        {
            while(n%i == 0)
            {
                n /= i;
                a.push_back(i);
            }
        }
    }
    else
        for(int i = 2; i * i < n; i++)
        {
            while(n%i == 0)
            {
                n /= i;
                a.push_back(i);
            }
        }
    return a;
}

i*i

• 어떤 수의 인수의 수는 제곱근의 2배또는 2배-1이다. 속도 개선에 도움이 된다.

if(n> 10)

• 매개변수 n이 3,4 등 너무 작을 경우 뒤에 나오는 i*i라는 조건 때문에 소인수의 모든 수를 구할 수 없게된다.

ex
i = 4 일경우
4의 소인수 1, 2
반복문순회 후 a에 할당된 수
1