SGU 102 Coprimes ---- 欧拉函数、素数的应用&&GCD水题 - c++编程基础

题意：为求不大于N并与N互质的正整数的个数。我们把这样的两个正整数称为是互质的：当且仅当它们的最大公约数为1。

欧拉函数：

#include   
#include   
  
using namespace std;  
  
const int maxisp = 1000 + 10;  
const int maxp = 500 + 10;  
  
int num,n;  
int prime[maxp];  
int isprime[maxisp];  
  
inline void get_prime()  
{  
    num=0;  
    for(int i=2;i<=maxisp;i++)  
        if(!isprime[i])  
        {  
            prime[num++]=i;  
            for(int j=1;j*i<=maxisp;j++)  
                isprime[i*j]=1;  
        }  
}  
  
inline int euler(int x)  
{  
    int res=x;  
    for(int i=0;i




1)  res=res/x*(x-1);  
    return res;  
}  
  
int main()  
{  
    get_prime();  
    while(~scanf("%d",&n))  
    {  
        if(n==1)    printf("1\n");  
        else    printf("%d\n",euler(n));  
    }  
    return 0;  
}

GCD模拟：

#include   
#include   
  
using namespace std;  
  
inline int gcd(int a,int b)  
{  
    return b gcd(b,a%b):a;  
}  
  
int main()  
{  
    int n;  
    while(~scanf("%d",&n))  
    {  
        int ans=0;  
        for(int i=1;i<=n;i++)  
            if(gcd(n,i)==1)ans++;  
        printf("%d\n",ans);  
    }  
}