C++ 소인수분해

알고리즘

C++ 소인수분해

Chars4785 2019. 1. 11. 21:51

소인수 분해

소수로 나누는 것들

#include <iostream>
#include <time.h>

using namespace std;


int num; // 입력받을 숫자
int k = 2; // 2부터 1씩 증가하는 숫자

int main() {

   cin >> num;
   
   while (num != 1) {
      if (num % k == 0) {
         cout << k <<endl;
         num /= k;
      }
      else {
         k++;
      }
   }
   return 0;
}

먼저 소수를 다 찾고 나누는 방식을 선택 했지만 , 시간이 너무 많이 걸린다.

#include <iostream>
#include <time.h>

using namespace std;

int prim[10000000];

void PrimNum(int num)
{
   int index=0;
   
   for(int i=2;i<=num;i++)
   {  
      bool flag = true;

      for(int j=2;j<i;j++)
      {
         if(i % j ==0)
         {
            flag =false;
            break;
         }
      }

      if(flag)
         prim[index++] = i;

   }

}

int main() {


   int num;
   cin >>num;

   int index=0;

   PrimNum(num);


   while(1)
   {

      if(num % prim[index] == 0 )
      {
         cout<< prim[index]<<endl;
         num /= prim[index];
         index =0;
         
      }else{
         index++;
      }


      if(prim[index]==0)
         break;


   }
   

   

   return 0;
}