title: C++ Coprimes Problem. Optimize code
body: <p>Hi i want to optimize the following code. It tries to find all coprimes in a given range by comparing them to n. But i want to make it run faster... any ideas?</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  using namespace std;
  
  int GCD(int a, int b)
  {
      while( 1 )
      {
          a = a % b;
    if( a == 0 )
     return b;
    b = b % a;
  
          if( b == 0 )
     return a;
      }
  }
  
  
  int main(void){
   int t;
   cin &gt;&gt; t;
   for(int i=0; i&lt;t; i++){
    int n,a,b;
    cin &gt;&gt; n &gt;&gt; a &gt;&gt; b;
  
    int c = 0;
    for(int j=a; j&lt;=b; j++){
     if(GCD(j, n) == 1) c++;
    }
  
    cout &lt;&lt; c &lt;&lt; endl;
   }
  
   return 0;
  }
  </code></pre>