Relative prime numbers

Two integers a and b are relatively prime if and only if there are no integers:


x > 1, y > 0, z > 0 such that a = xy and b = xz.

I wrote a program that determines how many positive integers less than n are relatively prime to n. But my program works too slowly because the number is sometimes too big.

My program should work for n <= 1000000000.

#include 
#include 
#include 
using namespace std;

int main()
{
    long long int n;
    int cntr = 0, cntr2 = 0;
    cin >> n;
    if (!n) return 0;
    vector  num;
    for (int i = 2; i 0)
            {
                for (int j = 0; j < num.size(); j++)
                {
                    if (i % num[j] != 0)
                        cntr2++;
                }
                if (cntr2 == num.size())
                    cntr++;
                cntr2 = 0;
            }
            else
                cntr++;
        }
        else
            num.push_back(i);
    }
    cout << cntr + 1 << endl;
}

In order to determine whether two numbers are co-prime (relatively prime), you can check whether their gcd (greatest common divisor) is greater than 1.
The gcd can be calculated by Euclid's algorithm:

unsigned int gcd (unsigned int a, unsigned int b)
    {
      unsigned int x;
      while (b)
        {
          x = a % b;
          a = b;
          b = x;
        }
      return a;
    }

if gcd(x,y) > 1: the numbers are not co-prime.

If the code is supposed to run on a platform with slow integer division, you can use the so called binary gcd instead.

StackExchange Code Review Q#39109, answer score: 5