求1-N中与N互质的数的个数被称为欧拉函数

/*
1~N中和N互质的数的个数
=N(1-1/p1)(1-1/p2)...(1-1/pk)=N((p1-1)/p1)((p2-1)/p2)...((pk-1)/pk)

1.从1-N中去掉p1,p2,...,pk的倍数

N-N/p1-N/p2-...-N/pk

2.加上所有pi*pj的倍数

+N/(p1p2)+N/(p1p3)+...

3.减去所有pi*pj*pk的倍数

-N/(p1p2p3)-N/(p2p3p4)

*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

int main()
{
    scanf("%d",&n);
    while(n--)
    {
        int x;
        scanf("%d",&x);
        int res=x;
        for(int i=2;i<=x/i;i++)
            if(x%i==0)
            {
                res=res/i*(i-1);
                while(x%i==0)
                    x/=i;
            }
        if(x>1)
            res=res/x*(x-1);
        printf("%d\n",res);
    }
    return 0;
}

筛法求欧拉函数
证明转载于： 点它

#include <iostream>
#include <cstring>
#include <algorithm>

#define MAXN 1000010

using namespace std;

typedef long long LL;

int primes[MAXN],cnt;
int phi[MAXN];
int st[MAXN];

LL get_eulers(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=1;
            if(i%primes[j]==0)
            {
                phi[primes[j]*i]=primes[j]*phi[i];
                break;
            }
            phi[primes[j]*i]=phi[i]*(primes[j]-1);
        }
    }
    LL res=0;
    for(int i=1;i<=n;i++)
        res+=phi[i];
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%lld",get_eulers(n));
    return 0;
}