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 &lt;= 1000000000.

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
using namespace std;

int main()
{
    long long int n;
    int cntr = 0, cntr2 = 0;
    cin &gt;&gt; n;
    if (!n) return 0;
    vector &lt;int&gt; num;
    for (int i = 2; i &lt; n; i++)
    {
        if (n % i != 0)
        {
            if (num.size()&gt;0)
            {
                for (int j = 0; j &lt; num.size(); j++)
                {
                    if (i % num[j] != 0)
                        cntr2++;
                }
                if (cntr2 == num.size())
                    cntr++;
                cntr2 = 0;
            }
            else
                cntr++;
        }
        else
            num.push_back(i);
    }
    cout &lt;&lt; cntr + 1 &lt;&lt; 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.