学步园

#include <iostream>
#include <conio.h>
#include <cstring>
// m^n % k
int quickpow(int a,int b,int n)
{
     int t = 1;

    if (b == 0)
        return 1;

    if (b == 1)
        return a%n;

    t = quickpow(a, b>>1, n);
    t = t*t % n;

    if (b&0x1)
    {
        t = t*a % n;
    }
    return t;
}
using namespace std;

int main()
{
    int p;
    //100以内素数表
    int prime[25]= {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};
    int pi[25];
    int i=0,j=0;
    int m;
    cout<<"请输入奇素数p"<<endl;
    while(cin>>p)
    {
        //标准素因子分解
        m=p-1;
        for(i=0; i<25; i++)
        {
            if(m%prime[i]==0)
            {
                while(m%prime[i]==0)
                {
                    m=m/prime[i];
                }
                //记录因数有哪些素数
                pi[j]=prime[i];
                j++;
            }
        }

        int num=j;

        //取整数pi   开始试
      /*  for(j=0; j<num; j++)
        {
            cout<<pi[j]<<endl;
        }
        getch();*/
        i=0,j=0;
        while(1)
        {
            if(quickpow(prime[i],(p-1)/pi[j],p)==1)
            {
                i++;
                j=0;
               // cout<<"failed!"<<endl;
            }
            else
            {
                //cout<<quickpow(prime[i],(p-1)/pi[j],p)<<endl;
                j++;
            }

            if(j==num)
            break;
        }
        cout<<"a="<<prime[i]<<"是p="<<p<<"的一个原根"<<endl;
        memset(pi,0,25*sizeof(int));
        j=0;
    }
    return 0;
}