ETF - Euler Totient Function

Tác giả: ladpro98

Ngôn ngữ: C++

#include <iostream>

using namespace std;

const int N = 1000006;

int phi[N], np[N], prime[N];
int nPrime;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    for (int i = 2; i < N; ++i) {
        if (!np[i]) prime[nPrime++] = np[i] = i;
        for (int j = 0; j < nPrime && prime[j] <= np[i] && prime[j] * i < N; ++j)
            np[prime[j] * i] = prime[j];
    }
    phi[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (np[i] == i) {
            phi[i] = i - 1;
            continue;
        }
        int j = i / np[i];
        if (j % np[i])
            phi[i] = phi[j] * phi[np[i]];
        else
            phi[i] = phi[j] * np[i];
    }
    int nTest; cin >> nTest;
    while (nTest--) {
        int n; cin >> n;
        cout << phi[n] << '\n';
    }
    return 0;
}

Download