Phân tích ra thừa số nguyên tố (Cơ bản)

SUU TAM

Cho số nguyên dương n (2<=n<=10^9) , hãy phân tích n ra thừa số nguyên tố.

Dữ liệu:

Một dòng duy nhất chứa số n.

Kết quả:

Mỗi dòng ghi một thừa số nguyên tố và số mũ tương ứng cách nhau bởi dấu cách.

Các thừa số nguyên tố in ra theo thứ tự tăng dần.

Ví dụ:

INPUT	OUTPUT
4	2 2
INPUT	OUTPUT
168	2 3 3 1 7 1

#include<iostream>
#include<math.h>
using namespace std;

int main()
{
    long n;cin>>n;
    int dem = 0;
    if(n%2 ==0)
     {
              do{ n>>=1;
               ++dem;}while(n%2==0);
               cout << 2 << " "<<dem<<endl;
     }
     if( n != 1){
     dem =0; 
     for( int i = 3;i<= sqrt(n);i +=2)
         {
         
              while(n%i == 0)
              {
                        n = n/i;
                        ++dem;
              }
              if( dem!=0)cout<< i <<" "<<dem<<endl;
              dem =0;
              
              }
        
     if(n!=1)cout<< n<<" "<<1;
     }
     //system("pause");
     return 0;
}