ETF

ETF - Euler Totient Function

#include <iostream>
#include <vector>

using namespace std;

const int N = 1000001;

vector<int> p;

void sieve()
{
    bool prime[N] = {false};

    for(int i = 3; i * i <= N; i += 2)
    {
        if(!prime[i])
        {
            for(int j = i * i; j <= N; j += i)
            {
                prime[j] = true;
            }
        }
    }

    p.push_back(2);

    for(int i = 3; i <= N; i += 2)
    {
        if(!prime[i])
            p.push_back(i);
    }

}


int main()
{
    int t, n;
    float result;

    cin >> t;

    sieve();

    while(t--)
    {
        cin >> n;

        result = n;

        for(int i = 0; i < p.size() && p[i] * p[i] <= n; i++)
        {

            if(n % p[i] == 0)
            {
                result *= (1.0 - 1.0 / (float)p[i]);

                while(n % p[i] == 0)
                    n = n / p[i];


            }
        }

        if(n > 1)
        {
            result *= (1.0 - 1.0 / (float)n);
        }

        cout << (int)result << endl;
    }
    return 0;
}