POJ 1284 Primitive Roots（原根）

素數的原根個數：p是素數，則p有φ(p-1)個原根（其中φ(p)表示p的歐拉函數）

代碼：

1：

[cpp]
#include <iostream>  
#include <cstdio>  
#include <string.h>  
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<k&&i*p[j]<50000; 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<<phi(n-1)<<endl; 
    } 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <string.h>
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<k&&i*p[j]<50000; 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<<phi(n-1)<<endl;
    }
    return 0;
}2：

[cpp]
#include <iostream>  
#include <cstdio>  
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<<phi(n-1)<<endl; 
    return 0; 
}