素因子分解(高速ふるい法&&試除法)

素因子分解のアルゴリズムはたくさんあって、フェルマ因子分解:試除法よりもっと効率的で、コンピュータの中で広く使われている多くのもっと有効な因子分解アルゴリズムの基礎です.二次ふるい法と数領域ふるい法は数百ビットの10進数の大きな数字に用いられる.数字が大きいほど数領域ふるい法が良い.今しばらくは基礎的な試除法しか書いていませんが、もっと良いアルゴリズムは私が勉強するのを待っています~~

#include <iostream>
#include<cstdio>
using namespace std;
const int N=5e6; //              ,                     
int pri[N],cnt; //50000      5133 
bool number[N+1];
void getprime()
{
cnt = 0;
for (int i = 2; i <= N; i++)//    
{
    if (!number[i]) pri[++cnt] = i;   //  means primer.
    for (int j = 1; j <= cnt && pri[j] * i <= N; j++)
    {
        number[i*pri[j]] = 1;
        if (i % pri[j] == 0)break;
    }
}
}
int main()
{
    getprime();
    //cout<<cnt<<endl;
    int n,i;
    while(cin>>n){
        if(n==1){printf("1=1
"); continue; }
        printf("%d=",n);
        int pow;
        bool p=0;
        for(i=1;i<=cnt;i++){
            p=0;    pow=0;
            if(n%pri[i]==0){
                printf("%d",pri[i]);
                n/=pri[i];
                pow=1;
            }
            while(n%pri[i]==0){
                p=1;
                pow++;
                n/=pri[i];
            }
            if(p)printf("^%d",pow);
            if(n==1){  printf("
");  break;  }
            if(pow)printf("*");
        }
    }
    return 0;
}