reducing a fraction/greatest common factor
I have the following way to find the GCF (greatest common factor) for two numbers, but I'm a little confused about the logic behind it. This is more of a math question if any, but...
Given 2 positive numbers p and q:
1. Store remainder of q divided by p into r.
2. While r is not 0:
__a. Copy p into q and r into p.
__b. Store remainder of q divided by p into r.
3. p is the GCF.
Lemme try that in code (should work...):
Code:
#include <stdio.h>
int find_gcf(int p, int q);
int main (void)
{
int p, q, gcf;
printf("Enter p:");
scanf("%d", &p);
printf("Enter q:");
scanf("%d", &q);
gcf = find_gcf(p, q);
printf("GCF of %d and %d is %d.", p, q, gcf);
return (0);
}
int find_gcf(int p, int q)
{
int r;
r = q % p;
while (r)
{
q = p;
p = r;
r = q % p;
}
return(p);
}
Now, what I understand out of this... according to some logic, if there's no remainder after the division, the denomenator is the GCF, that makes sense. Also, I'm trying to make sure that this is correct:
if there's some whole number answer as well a remainder, both of these should be divisible by the GCF. This is because the numerator is initially divisible by GCF, if we subtract some integer multiple of the GCF from it (which is what the whole # answer is), the remainder is still divisible by GCF.
We can now look at the remainder and the denomenator, which are two smaller numbers then previously, but still divisible by GCF. By repeating this procedure (thus the while loop), we should be able to reach a point when there's no remainder...
I don't know, it kinda makes sense to me, but still a bit fuzzy. Does anyone have a better explanation, or better yet, a better and more efficient way to find the GCF of 2 numbers through code?