Euler's Phi Function(Brute Force)

Euler's Phi Function(Brute Force).cpp

#include<bits/stdc++.h>

using namespace std;

int gcd(int a,int b){
        if(a%b==0) return b;
        else gcd(b,a%b);
}

int main(){
        int n,i,cnt=0;
        scanf("%d",&n);

        for(i=1;i<=n;i++){
                if(gcd(i,n)==1) cnt++;
        }
        printf("Phi( %d ) = %d\n",n, cnt);

        return 0;
}