finding greatest common denominator

[impseth]

The exercise in the book I'm reading wants you to take a fraction and bring it to lowest terms.
A few minutes ago I actually had a fair sized post asking for help because I couldn't get the code below to work. Then I had a house, and I saw what was wrong.

Behold! I spent about 3 hours on this exercise determined not to use the code in the book in order to find lowest terms.
Maybe this will help other people as well but mainly I just want to brag. I feel somewhat proud that I could fix the code below instead of using what the book gave me.

Here's the pseudo-code:

Take a fraction num/den
Divide the top number by every number from n(2) to num
If num divided by n does not have a remainder then I have found a number that can divide evenly into the numerator (numdiv)
If not increase n by 1 and try again, keep trying until num % n = 0
Do the same thing to the bottom number
(dendiv) becomes the number that can divide evenly into the denominator
If numdiv and dendiv are the same I have found a number that can divide evenly into both numerator and denominator
Because I'm counting backwards that number divided into both will give the fraction in lowest terms


Here is my code:

f_gcd()
{
  int numdiv = 1, dendiv = 0;
  int n = 2, d = 2, num, den;

  while (numdiv != dendiv)
  {
    for (; n < num; n++)
    {  
      if (num % n == 0)
      {
        numdiv = num / n; 
        n++;
        break;
      }
    }
    
    for (; d < den; d++)
    {
      if (den % d == 0)
      {
        dendiv = den / d;
        d++;
        break;
      }
    }

    if (numdiv == dendiv)
    {
      num = num / numdiv;
      den = den / dendiv;
    }
  }
}

Before it would just keep looping without increasing n past 2 or d past 3.
When I realized that the breaks were stopping n and d from increasing the n++ and d++ gave the right results. And if anybody's wondering, n and d have to start at 2 otherwise it'll be a divide by 0 or numdiv and dendiv will always be 1.

[jsmith]

wikipedia gives several far more efficient (and simple) algorithms for this.

not to burst your bubble...