Mathematical manipulation

Given a number n, find the total numbers, less than or equal to n which have at-least one common factor with n other than 1.

• Time : O(nlogn)
• Space : O(1)

class Solution {
    int gcd(int p, int q) {
        if(!q) return p;
        return gcd(q, p % q);
    }
public:
    int CommonFactor(int n){
        int res = 0;
        for(int i = 2; i <= n; i++)
            if(gcd(n,i) != 1) res++;
        return res;
    }
};