How do you find the GCF of 2 integers?

Question

I need to write a program which asks the user for two non-negative integers an then prints the Greatest Common Factor (GCF) of the two numbers. How would I do this in C++?

I forgot to mention it needs to use a while loop. Sorry.

Answer 1

Here is the algorithm referenced above:

#include
#include

int getGcf( int a, int b )
{
if ( a == b )
return a;
else if ( a < b )
getGcf( a, b - a );
else if ( a > b )
getGcf( a - b, b );
}

int main()
{
int g = getGcf( 25, 5 );
printf( "The GCF is: %d\n", g );

return EXIT_SUCCESS;
}

Very well, with a while loop:

#include
#include

int igcf( int a, int b )
{
while ( a != b )
{
if ( a < 1 || b < 1 )
return -1;

if ( a < b )
b = b - a;

else if ( b < a )
a = a - b;
}
return a;
}

int main()
{
printf( "Your GCF is: %d\n", igcf( 100, 10 ) );
return EXIT_SUCCESS;
}

Answer 2

Consider the fact that if m factors a and b (definition of a common factor), then m also factors a - b.
You can also use the Euclidean algorithm, since you have access to modulus. See the source for details.