求原根

今天学了数论。。。求原根真的好暴力
设模数为p,
我们把$p-1$p−1分解质因数，$p_1,p_2 \ldots p_m$p1​,p2​…pm​对于每一个$2 \leq i \leq p-1$2≤i≤p−1 ,判断$i^{p-1 \over p_j} \%p$ipj​p−1​%p是否为1，如果是，那么这个数就不是原根，否则就是
AC Code

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int zys[50];
int p;
int o;
int n;
int ksm(int a,int c,int b)
{
	long long re=1;
	long long t=a;
	while(c)
	{
		if(c&1)re=re%b*t%b;
		t=t%b*t%b;
		c>>=1;
	}
	return re;
}
int pd(int x)
{
	for(int i=1;i<=o;i++)
	{
		if(ksm(x,(p-1)/zys[i],p)%p==1)return 0;
	}
	return 1;
}
int main()
{
	scanf("%d",&p);
	int pp=p;
	p--;
	for(int i=2;i<=sqrt(p);i++)
	{
		if(p==1)break;
		if(p%i==0)
		{
			o++;
			zys[o]=i;
			while(p%i==0)
			{
				p/=i;
			}
		}
	}
	if(p!=1)
	{
		o++;
		zys[o]=p;
	}
	p=pp;
	for(int i=2;i<p;i++)
	{
		if(pd(i))
		{
			printf("%d",i);
			break;
		}
	}	
	return 0;
}