To P2 之 a010質因數分解

參考程式碼 ，最後有另一組建質數表的 genp程式
// a010
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#define maxn 46340  // sqrt(2147483647) < 46341
using namespace std;
bool c[maxn+10];
vector <int> p;    // 2~46340之間的質數共有 4792個，p[4791]=46337 ,前46327後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;     
}
// 篩法
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(); 

  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
*/

genp 建質數表-2

#include <iostream>

#include <cmath>

#include <vector>

#define MaxN 2147483647

using namespace std;

vector <int> p;

bool isp(int n)

{

   int i,ps=p.size();

   int qn=sqrt(n);

   if (  !((n %6==1)or(n%6==5))  ) return 0;

    for(i=0;i<=qn;i++)

     if( !(n%p[i]) ) return 0;

   return 1;  

}

void gen_p(int n){

  int k,gap;

  int q=int(sqrt(float(n)));

//  cout<<n<<", sqrt="<<q<<endl;

  p.push_back(2);p.push_back(3);

  for(k=5,gap=2; k<=q; k+=gap)

   { gap=6-gap;

     if(isp(k)){

       // cout <<k<<"  ";

       p.push_back(k); }

   }

  // cout<<endl;

}

int main()

{

    int n;

    gen_p(MaxN);

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

    cin>>n;

    cout <<n<<":"<<isp(n);

    return 0;

}