Cerința

Se dau n numere naturale nenule. Aflaţi pentru fiecare număr dat x, câte numere naturale nenule mai mici sau egale cu x sunt prime cu x?

Date de intrare

Fișierul de intrare eratostene3.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire eratostene3.out va conține pentru fiecare număr x din fişierul de intrare, numărul de numere naturale nenule mai mici sau egale cu x, prime cu x.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu

eratostene3.in

3
4 7 12

eratostene3.out

2 6 4

Explicație

Numerele prime cu 4, mai mici sau egale cu 4, sunt: 1,3.
Numerele prime cu 7, mai mici sau egale cu 7, sunt: 1,2,3,4,5,6.
Numerele prime cu 12, mai mici sau egale cu 12, sunt: 1,5,7,11.
Vezi Indicatorul lui Euler.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("eratostene3.in");
ofstream cout("eratostene3.out");

int E[1000001], n;
long long int t;

int main(){
    cin >> n;
    for(int i = 1; i <= 1000000; ++i)
        E[i] = i - 1;
    E[1] = 1;
    for(int i = 2; i <= 1000000; ++i)
        for(int j = 2 * i; j <= 1000000; j = j + i)
            E[j] = E[j] - E[i];
    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        cout << E[x] << ' ';
    }
    return 0;
}