[알고리즘] ACM - 소인수 분해 문제

조건..

1.  곱해서 자신이 되는 인수들의 집합의 경우의 수를 찾아 출력하고 인수들의 집합을 출력한다.(1과 자기자신 제외) 

2. 인수들의 집합이 출력될때는 사전식으로 정렬(오름차순)되어 출력한다. 

3. 중복되는 집합 경우(3X4, 4X3)은 경우의 수를 한가지로 둔다.

main code

void Factorize()

{

         // 1은 인수에서 제외하므로 2부터 시작

         // 끝은 해당 수의 제곱근까지만 카운트

         for(int i=2; i <= sqrt((float)Factors[Fac_index]); i++)

         {

                  // 나누어 떨어진다면 i는 인수이다.

                  if(Factors[Fac_index]%i ==0)

                  {

                           // 중복되는 수를 제거하기 위해 앞에 인수가 뒤에 인수보다 작아야 한다.

                           if((i >= Factors[Fac_index-1]) || (Fac_index == 0))

                           {

                                   // 나눈몫을 다음 배열에 넣음

                                   // 인수는 원래 값을 대체함.

                                   // 배열에는 인수들이 들어간다. (오름차순으로)

                                   Factors[Fac_index+1] = Factors[Fac_index]/i;

                                   Factors[Fac_index] = i;

                                  

                                   // index를 다음으로 옮긴다.

                                   // 그리고 대상 수를 다시 인수분해

                                   Fac_index++;

                                   Factorize();

                                  

                                   // 더 이상 나눌수 없을 때 해당 배열 출력

                                   // 이때가 한가지 경우가 됨.

                                   for(int j=0; j<= Fac_index ; j++)

                                   {

                                            cout << Factors[j] << " " ;

                                   }

                                   cout << endl;

 

                                   // 제일 뒤에 두수를 곱해서 제일 뒤에 수 바로 앞에 넣는다.

                                   // 그리고 해당수를 다른 인수로 인수분해 시도한다.

                                   Factors[Fac_index-1] = Factors[Fac_index-1]*Factors[Fac_index];

                                   Fac_index--;

                           }                         

                  }

         }

}