title: Relative prime numbers
body: <p>Two integers a and b are relatively prime if and only if there are no integers  </p>
  
  <blockquote>
    <p>x > 1,  y > 0, z > 0 such that a = xy and b = xz.  </p>
  </blockquote>
  
  <p>I wrote program that determine how many positive integers less than n are relatively prime to n, but my program work too slow because sometimes number is too big. Can you fix my program.<br>
  My program should work for n&lt;=1000000000<br>
  Here is my code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;algorithm&gt;
  using namespace std;
  
  int main()
  {
      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;
  }
  </code></pre>