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;
}