素数的原根个数：p是素数，则p有φ(p-1)个原根（其中φ(p)表示p的欧拉函数）
代码：
1：
[cpp]
#include
#include
#include
using namespace std;
bool boo[50000];
long long p[20000];
void prim()//线性筛素数，在main函数里面先调用函数prim
{
memset(boo, 0, sizeof (boo));
boo[0]=boo[1]=1;
int k=0;
for (int i=2; i<50000; i++)
{
if (!boo[i]) p[k++]=i;
for (int j=0; j
boo[i*p[j]]=1;
if (!(i%p[j])) break;
}
}
}
long long phi(long long n)
{
long long rea = n;
for (int i=0; p[i]*p[i]<=n; i++)//对于一些不是素数的可以不用遍历
{
if (n%p[i]==0)
{
rea-=rea/p[i];
do
n/=p[i];
while (n%p[i]==0);
}
}
if (n>1)
rea-=rea/n;
return rea;
}
int main()
{
int n;
prim();
while (cin>>n)
{
cout<
return 0;
}
#include
#include
#include
using namespace std;
bool boo[50000];
long long p[20000];
void prim()//线性筛素数，在main函数里面先调用函数prim
{
memset(boo, 0, sizeof (boo));
boo[0]=boo[1]=1;
int k=0;
for (int i=2; i<50000; i++)
{
if (!boo[i]) p[k++]=i;
for (int j=0; j
boo[i*p[j]]=1;
if (!(i%p[j])) break;
}
}
}
long long phi(long long n)
{
long long rea = n;
for (int i=0; p[i]*p[i]<=n; i++)//对于一些不是素数的可以不用遍历
{
if (n%p[i]==0)
{
rea-=rea/p[i];
do
n/=p[i];
while (n%p[i]==0);
}
}
if (n>1)
rea-=rea/n;
return rea;
}
int main()
{
int n;
prim();
while (cin>>n)
{
cout<
return 0;
}2：
[cpp]
#include
#include
using namespace std;
long long phi(long long n)
{
long long rea = n;
for (int i=2; i*i<=n; i++)
{
if (n%i==0)
{
rea-=rea/i;
do
n/=i;
while (n%i==0);
}
}
if (n>1)
rea-=rea/n;
return rea;
}
int main()
{
int n;
while (cin>>n)
cout<
}