104M-P11 質因數分解(CPP版參考)

參考程式碼1
#include <iostream>
#include <cstring> // memset
#include <vector> // vector
#include <cmath>  // sqrt

/* size(255): 54, 251
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251  

size(46340):4792,46337
*/
using namespace std;
const int MaxN = 255;   //也可以 46340=sqrt(2147483647); 
                 // 這一題只要 255=sqrt(65535); 即可   //
vector <int> p;
bool c[MaxN+1];
void print()  //印質數測試用
{
for(int j=1,i=0; i<p.size() && p[i]<=255; ++i,++j)
{
cout << p[i] <<' ';
if(j%10==0) cout << endl;
}
cout << " size:" << p.size() <<"," << p[p.size()-1] << endl;
}
void gen1() // 以 篩法建質數表 p [2~MaxN] 的質數
{
int i,j;
p.clear();  // 將 p 清空
memset(c,false,sizeof(c)); // c全設為false
c[0] = c[1] = true;  // true 非質數
for (i=2; i<=MaxN; ++i)
{
if(c[i]==false)
{
p.push_back(i);
for(j=i+i; j<=MaxN; j+=i)
c[j] = true;
}
}
//  print();  // print for test
}
int main(void)
{
int t , i,j,k , n;
gen1();  // 以 篩法建質數表 p // 
cin >> t;  //有 t 個數字

while( t-- ) // 共 t 個 數字 倒數至 0
{
cin >> n;
for(i=0; i<p.size() && n>1;  ++i)
{
int cnt=0;
while( n%p[i] == 0)
{
n/=p[i];
++cnt;  //次方數
}
if(cnt)cout << p[i] <<'^'<< cnt <<' ';
}
if(n>1) cout << n <<"^1" ;

cout << endl;
}
return 0;
}
/* 輸入
9
20
8
30
54
81
881
512
808
1111
-------輸出
2^2 5^1
2^3
2^1 3^1 5^1
2^1 3^3
3^4
881^1
2^9
2^3 101^1
11^1 101^1

*/

參考程式碼2:  {另一種建質數表} gen2, isp

#include <iostream>

#include <cstring> // memset

#include <vector> // vector

#include <cmath>  // sqrt

using namespace std;

const int MaxN = 255;   //也可以 46340=sqrt(2147483647); 

           // 這一題只要 255=sqrt(65535); 即可   //

vector <int> p;

void print()

{

for(int j=1,i=0; i<p.size() && p[i]<=255; ++i,++j)

{

cout << p[i] <<' ';

if(j%10==0) cout << endl;

}

cout << " size:" << p.size() <<"," << p[p.size()-1] << endl;

}

bool isp(int k)

{

int q=int(sqrt(k));

for(int i=2; i<=q; ++i)

  if(k%i==0) return false;  // 被 i 整除 非質數

return true;  // 2 ~ sqrt(k) 都沒整除，即是質數

}

void gen2() // 以 isp(k) 建質數表 p [2~MaxN] 的質數

{

int i,j;

p.clear();  // 將 p 清空

p.push_back(2); // 2 第1個 質數

for (i=3; i<=MaxN; i+=2)  //測試 3 ~ MaxN 的所有奇數

{

if( isp(i) ) p.push_back(i);

}

//  print();  // print for test

}

struct fp

{

int p; //含有的質因數 

int f; //該質因數的次方 

};

vector < fp > f;

int main(void)

{

int t , i,j,k , n;

gen2();       // 以 isp 建質數表 p  // 

cin >> t;  //有 t 個數字

while( t-- ) // 共 t 個 數字 倒數至 0

{

cin >> n;

f.clear();

for(i=0; i<p.size() && n>1;  ++i)

{

int cnt=0;

while( n%p[i] == 0)

{

n/=p[i];

++cnt;  //次方數

}

fp fp1;

fp1.p=p[i];  fp1.f=cnt;

if( cnt )   f.push_back(fp1);          

}

if(n>1) cout << n <<"^1" << endl;

else

{

for(i=0; i<f.size(); ++i)

 cout << f[i].p <<'^'<< f[i].f <<' ';

cout << endl;

}

}

return 0;

}