C++,求大数 (p^n-1) 的质因子分解,其中p为素数,n为整数.

C++,求大数 (p^n-1) 的质因子分解,其中p为素数,n为整数.
例如 p＝2,n＝100．输出　(p^n-1)　的素因子分解.
再如p＝3,n＝100．输出　(p^n-1)　的素因子分解.
涉及到大数分解的问题!

/*
m的p次方减去1等于（m^0+m^1+m^2+...+m^(p-1)）*（m-1）,
若不考虑（m-1）,则剩余部分m^0+m^1+m^2+...+m^(p-1)
可以用m进制数表示,即111111...1111(m),m进制数,有p个1,
然后利用m进制数的除法判断一个数是否能被整除来分解质因数
*/
#include <iostream>
#include <bitset>
#include <ctime>
using namespace std;

bitset<100002> bits;

//找到质数 
void set_prim()
{    
    clock_t start,end;
    start=clock();
    bits.set(); int i=2,k;
 
    while(true)
    {
        while(bits[i]==0)  {++i;  if(i>400) break;}
        if(i<100001)
        {
        for(int j=i;j<100001;j=j+i) {if((i+j)<100001)  bits.reset(i+j);}
        ++i;}
        if(i>100000)  break;
    }
    end=clock();
    cout<<"找到<100000质数用时"<<(double)(end - start) / CLOCKS_PER_SEC
    <<"秒"<<endl;
    
    int counter=0;
   for(int i=1;i<100001;++i)    {
        if(bits[i])  ++counter;
    }  
    cout<<"质数数量是："<<counter<<endl;    
}
//这里只计算100000以下的质因数,
//如果想能分解出更大的质因数,
//可以加大MAXSIZE的值

const int MAXSIZE = 100000;

//定义一个结构体,主要需要它的长度
typedef struct 
{
    int xx[1000];
    int length;
}Sqlist;

//m_num用于将待测试的数存为m进制数,
//arr初始化为11111.11111(m进制,p个）,高位在后
//temp1用于临时储存商和余数的m进制数,高位在后
//temp2用于储存商（while循环后的）,高位数在前（数组的0位置）
//copy1用于备份arr
//b就是为了实现rev,可有可无
Sqlist m_num,arr,temp1,temp2,copy1,b;

//将数组倒叙
Sqlist& rev(Sqlist& a)
{
    b.length=a.length;
    for(int i=0;i<a.length;++i)
    {
        b.xx[i]=a.xx[a.length-i-1];
    }
    return b;
}

//将十进制数转化为m进制数
void to_m(Sqlist& m_num,int m,int val)
{
    int i=0;
    while(val>0)
    {       
        m_num.xx[i]=val%m;
        ++i;
        val=val/m; 
    }
    m_num.length=i;
}

//将m进制数（数组）转化为十进制int,
//转化beg到end部分,物理位置
int to_dec(Sqlist& a,int beg,int end,int m)
{
//    cout<<"beg="<<beg<<" end="<<end<<" m="<<m<<endl;
    int val=0;
    int mul=1;
    for(int i=beg;i<=end;++i)
    {
        val+=a.xx[i]*mul;
        mul*=m;
    }
    return val;
}

//m进制数除法,判断是否整除,并得到除后的结果
//如果不整除,arr内容不变
bool division(Sqlist& arr,Sqlist& m_num,int m)
{
    temp2.length=0;
    for(int i=0;i<arr.length;++i)
    copy1.xx[i]=arr.xx[i];
    copy1.length=arr.length;
    
//    cout<<"copy is: "<<to_dec(copy1,0,copy1.length-1,m)<<endl;
    
    int site=arr.length-m_num.length;
    //类似竖式除法,site记录对齐时最后一个位置
    int key=to_dec(m_num,0,m_num.length-1,m);
//    cout<<"key= "<<key<<endl;
    int val;
    int con=0; //记录每次得到的商
    int rem=0; //记录每次得到的余数
    int len=m_num.length;  //记录要除的数的长度（m进制）
    int beg=0,end=0;    //记录temp2要插入的位置
    int counter=0;      //没什么用,就是防止第一次除法商为0记录    //下来,其实没有必要,以为arr初始为1111...11111,第一次商
    // 必然大于0
    

    //主循环,每循环一次,site减1,就像竖式除法每次后移一位
    while(site>=0)
    {
        val=to_dec(arr,site,arr.length-1,m);
        con=val/key; rem=val%key;
        if(counter!=0){
        if(con==0) //商是0说明不够除,故商0,加一位继续除
        {
            temp2.length++;
            temp2.xx[end]=0;
            end++;
            --site;
            continue;//直接进入while的喜爱一次循环
        }
        }    
        counter++;
        
        //把商变为m进制,并存入temp2中,
        //高位在前是因为商是一位一位得到的,从高到低向后
        to_m(temp1,m,con);

        beg=end; end=beg+temp1.length;
        temp2.length+=temp1.length;
        for(int i=beg;i<end;++i)
        {
            temp2.xx[i]=temp1.xx[end-i-1];
        }
        
        //把余数变为m进制,并写进arr数组,为了下一次竖式除法
        to_m(temp1,m,rem);
        arr.length=site+temp1.length;
//        cout<<"arr's length is: "<<arr.length<<endl;
        --site;
        int temp_len=temp1.length-1;
        for(int i=arr.length-1;i>site;--i)
        {
            arr.xx[i]=temp1.xx[temp_len];
            --temp_len;
        }
        
//        cout<<"site is: "<<site<<endl;
//        cout<<temp2.length<<endl;
//        cout<<"临时结果："<<to_dec(rev(temp2),0,temp2.length-1,m)<<endl; 
    }//end while
    
    bool flag=true;
    //判断是否为整除,若整除arr变为temp2,否则返回到copy1
    for(int i=0;i<arr.length;++i)
    if(arr.xx[i]>0) 
    {        
        flag=false;
        //如果有一位大于0,说明不整除
    }
    
    //整除时
    if(flag==true){   
         for(int i=0;i<temp2.length;++i)
        {
            arr.xx[i]=temp2.xx[temp2.length-i-1];
        }
        arr.length=temp2.length;
    } 
    //不整除时
    else if(flag==false)
    {
        for(int i=0;i<copy1.length;++i)
        {
            arr.xx[i]=copy1.xx[i];
        }
        arr.length=copy1.length;

    }
    return flag;
}

int bo[MAXSIZE]; //用物理位置表示数,里面存的数据表示
//能分解出该数的个数,0表示不被分解出它

int main()
{ 
    set_prim();   
    int m,p;
    cout<<"m进制数"<<endl;
    while(cin>>m>>p)
    {
        for(int i=0;i<1000;++i)
        temp2.xx[i]=0;
        
        for(int i=0;i<20000;++i)
        bo[i]=0;
        
        for(int i=0;i<p;++i)
        arr.xx[i]=1;         
        arr.length=p;
          

       int mm=m-1; //这个是m^0+m^1+m^2+...+m^(n-1)还要乘以的m-1
       for(int i=2;i<m;++i)//数据较小,直接连续分解
       {
           while(mm%i==0)
           {
               bo[i]++;
               mm/=i;
           }
       }   
       
       to_m(m_num,m,2);
       while(division(arr,m_num,m))
       {
          ++bo[2];
       }
           
       for(int i=3;i<MAXSIZE;i+=2)
       {
           if(bits[i])
           {
               to_m(m_num,m,i);
               while(division(arr,m_num,m)) ++bo[i];
           }
       }
       
       for(int i=2;i<MAXSIZE;++i)
       {
           if(bo[i]>0)
           {
               cout<<bo[i]<<"个"<<i<<" "; 
           }
       } 
       cout<<endl;  
        
    } 
}我这个程序只是分解出100000一下的质因数,想要分出更大的,可以相应放大来查找,很容易.也可以去掉bo数组,每次一输出,降低内存使用. 2的19次方-1下面什么都没输出说明它没有小于100000的质因数.