অয়লার এর টোশেন্ট ফাংশন (Euler's Totient Function) {শুধুমাত্র একটি সংখ্যা n এর জন্য}

Standard
n এর থেকে ছাট বা সমান এমন কতগুলি সংখ্যা  আছে যা n এর সাথে coprime।   coprime অর্থ হল তাদের ১ ছাড়া কোন সাধারণ গুণনীয়ক নেই।
/**Bismillahir Rahmanir Rahim.**/

#include <bits/stdc++.h>

using namespace std;

int Phi(int n)
{
    int ans = n;
    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0)
        {
            while(n%i==0)
                n/=i;
            ans -= ans/i;
        }
    }
    if(n>1) ans -= ans/n;
    return ans;
}
int main()
{
    int n;
    scanf("%d", &n);
    int ans = Phi(n);
    printf("Number of Coprime for %d is %d\n", n, ans);
    return 0;
}