2015年8月26日 星期三

C++進階研習: a010因數分解

           No comments   
// zerojudge.tw 的 a010 質因數分解
//   建質數表較費事，若資料不多不一定要建表，像a007有十萬筆就一定要建表
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#define maxn 46340  // sqrt(2147483647) < 46341
using namespace std;
bool c[maxn+10];  //0~46340之間false為質數
vector <int> p;    // 2~46340之間的質數共有 4792個
//  p[4791]=46337 , p[4790]=46327，p[4792]=46349

// 以下 isp 為函式， 傳入 n 判斷是否為質數
bool isp(int n)
{
  if(n<=maxn) return( !c[n] );
  int q = (int) sqrt(n);
  int k;
  for(k=0; k<p.size() && p[k]<=q ; ++k)
    if(n%p[k]==0) return false;
  return true;    
}
// 篩法建 c[0..46340] 及 vector <int> 
void sieve()
{
  int i,j,k;
  memset(c,0,sizeof(c));
  c[0]=c[1]=1;
  for(i=2;i<=maxn;++i)
  {
     if(c[i]==1) continue; //非質數
     p.push_back(i);  // i是質數，放入 p 中
     //是質數的倍數 註記為非質數
     for(j=i+i; j<=maxn; j+=i)
       c[j]=1;                  
  }
  //  for(k=2; k<=100; ++k)  // 印出 2~100的質數
//    if( !c[k] ) cout << k << endl;
//  cout << p.size() <<" " << p[p.size()-1] << endl;
  return ;
}
// 主程式
int main()
{
  sieve(); //建質數表，有bool c[] 及 vector <int> p
  int n;
  while( cin >> n ) 
  {
         int i=0, f=0;
         bool lead=true;
    while( n>1 && i<p.size() )
    {
            if(n%p[i]==0)
                 {
                    n/=p[i];
                         ++f;      
                 }
                 else
                 {
         if(f>0)
                        {
                                if(lead) lead=false; else cout <<" * ";
                                 cout <<p[i];
               if(f>1) cout <<"^" <<f;
           f=0;
                   }
                        ++i;
                 }
         }
         if(n>1 || f>0)
         {
                   if(lead) lead=false; else cout <<" * ";  // n>1 及 f>0 不同時
         if(f>0) cout <<p[i];
         if(f>1) cout <<"^" <<f;
         if(n>1) cout << n;
        }
    cout << endl;
  }
  return 0;
}
/*
範例輸入 ：
20
17
999997
288
614017530
92822
2147210123
範例輸出 ：
2^2 * 5
17
757 * 1321
2^5 * 3^2
2 * 3^3 * 5 * 7^2 * 46411
2 * 46411
46327 * 46349

*/