프로그래머스 - 소인수분해 - C++

https://school.programmers.co.kr/learn/courses/30/lessons/120852

프로그래머스

 

#include <string>
#include <vector>
#include <map>
using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    bool arr[10001]={0,};
    
    int num = n;
    
    while(true)
    {
        bool ch=false;
        for(int i=2;i<=n;i++)
        {
            if(n%i==0)
            {
                n/=i;
                arr[i]=true;
                ch=true;
                break;
            }
        }    
        if(ch==false)
        {
            arr[n]=true;
            break;
        }
    }
    for(int i=2;i<=num;i++)
    {
        if(arr[i]==true)answer.push_back(i);
    }
    
    
    return answer;
}

 

설명

 

n을 소인수분해하여 소인수를 중복없이 출력하는 문제이다. 

우선 소인수가 어떤 것이 있는지를 저장하기 위해서 bool arr[10001] 배열을 생성하였다. 

bool arr[10001]={0,};

만약 소인수 중 2가 있다면 arr[2]= true 로 저장된다. 

 

그리고 소인수 분해를 while문 안에서 진행한다. 

while(true)
    {
        bool ch=false;
        for(int i=2;i<=n;i++)
        {
            if(n%i==0)
            {
                n/=i;
                arr[i]=true;
                ch=true;
                break;
            }
        }    
        if(ch==false)
        {
            arr[n]=true;
            break;
        }
    }

소인수는 소수인 인수를 뜻하기 때문에 2부터 시작한다. 

for문에서 나누어 떨어지는 수를 찾고 만약 있다면 arr[i]를 참으로 바꾸고 

n을 i로 나눈다. 

그리고 ch를 true로 바꾸고 for문을 빠져나온다. 

 

이 ch는 for문을 빠져나오고 소인수로 n이 나눠졌는지를 판단한다. 

나눠지지 않았다면 그 자신이 소수라는 소리이므로 소인수 분해를 종료한다. 

 

ex) n=6 이면,

n이 for문에서 2로 나누어지며 arr[2] 는 true가 되고 n은 3이된다.

나누어지는 수가 있었기 때문에 if문에 들어가지 않고 다시 while문을 돈다.

이 때, 3은 나누어지지 않기 때문에 if문에서 arr[3]= true가 되고 while문이 종료된다. 

 

그리고 arr배열에서 true인 값을 answer에 차례로 대입하면 [2,3] 이 된다.