例えば、6のオイラーのトーシェント関数を求める場合：6=2×3なので、そのトーシェント関数は6×(2-1)/2×(3-1)/3となります。
原理：1~NのうちNと互いに素な数の個数は、NからNと互いに素でない数を引いたものに等しくなります。Nと互いに素でない数はNの因数の倍数によってふるい落とされますが、一部の数は複数の因数によって複数回ふるい落とされるため、因数の積の倍数を加算する必要があります（原理の簡単な説明、ここでは証明は省略）

#include<iostream>
using namespace std;
typedef long long ll;
ll num, limit;

int main()
{
    cin >> limit;
    while (limit--)
    {
        cin >> num;
        ll result = num;
        for (int factor = 2; factor <= num / factor; factor++)
        {
            if (num % factor == 0) result = result * (factor - 1) / factor;
            while (num % factor == 0) num /= factor;
        }
        if (num > 1) result = result * (num - 1) / num;
        cout << result << endl;
    }
}

前提知識：線形ふるい法による素数の求め方

原理：合成数はその最小素因数によってふるい落とされ、残ったものが素数となります

//prime線形ふるい法による素数の求め方、各合成数がその最小素因数によってふるい落とされることを保証し、prime配列で素数を記録し、v配列で各数の最小素因数を記録（同時にふるい落とされたかどうかのマークとしても機能） //例えば 2 3 4 5 6 7 8 9 10 11 12 という数列（下のコードと併せて理解してください） 2は未使用なので、prime配列に追加され、2はprime配列を一通り走査して4をふるい落とします。v[4]==2はその最小素因数が2であることを示します。 3は未使用なので、6と9をふるい落とします 4は2でマークされているため、prime配列に追加されず、prime配列[2,3]を走査して8をふるい落としますが、12はふるい落とされません。なぜなら12の最小素因数は2であり、12はi==6のときに6×2によってふるい落とされるべきで、3ではないからです。

#include<iostream>
#include<vector>
using namespace std;
const int MAX_N = 1000010;
int n, prime_count = 0;
int prime[MAX_N], v[MAX_N];
int main()
{
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        if (v[i] == 0) {
            v[i] = i;
            prime[++prime_count] = i;
        }
        for (int j = 1; j <= prime_count; j++)    
        {
            if (prime[j] > v[i] || prime[j] * i > n) break;
            v[i * prime[j]] = prime[j];
        }
    }
    for (int i = 1; i <= prime_count; i++)
        cout << prime[i] << ' ';
}

線形ふるい法によるオイラーのトーシェント関数の計算（オイラーのトーシェント関数は積性関数）

下記コード：phi[i * prime[j]] = phi[i] * prime[j] //prime[j]はiの因数

原理：{ なぜならprime[j]はiとiprime[j]の共通因数であり、**オイラーのトーシェント関数ϕ(N) = N×(p1−1)/p1×(p2−1)/p2×…×(pm−1)/pmから、phi[iprime[j]]のオイラーのトーシェント関数を求めるには、phi[i]の基数Nをprime[j]倍だけ拡大**すればよいからです } phi[i * prime[j]] = phi[i] * (prime[j] - 1); //prime[j]はiの因数ではない なぜならprime[j]はiの因数ではないが、prime[j]*iの因数であるため、まずphi[i]の基数をprime[j]倍拡大し、新しいprime[j]の因数を追加するため、(prime[j]-1)/prime[j]を乗算し、最終的にphi[i * prime[j]] = phi[i] * (prime[j] - 1)と簡略化できます。

#include<iostream>
using namespace std;
typedef long long ll;
const int MAX_N = 1000010;
ll num, limit, prime_count = 0;
ll prime[MAX_N], v[MAX_N], phi[MAX_N];

ll calculate_euler()
{
    phi[1] = 1;
    for (int i = 2; i <= limit; i++)
    {
        if (v[i] == 0) {
            prime[++prime_count] = i;
            phi[i] = i - 1; //iが素数の場合、互いに素な数の個数はi-1
        }
        for (int j = 1; j <= prime_count && prime[j] * i <= limit; j++)
        {
            v[prime[j] * i] = prime[j];
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    ll total = 0;
    for (int i = 1; i <= limit; i++) total += phi[i];
    return total;
}

int main()
{
    cin >> limit;
    cout << calculate_euler();
}