How do you get the gcf in c programming language?

Answer 1

Algorithm: to find HCF of two nos a, b 1. Find larger of two and let it l, smaller = s 2. divide l by s and find qotient (q) & remainder(r) 3. if r is 0 then s is the hcf 4. put l=s, s=r and go to step 2 int a, b; int l,s,q,r; if (a>b) {l=a;s=b;} else {l=b;s=a;} do {q= l/s; r=l%s; if (r != 0) {l=s;s=r} } while (r != 0); hcf=s; /* this variable to be output or returned as a function value as per programmer's convenience */

Answer 2

Just write a function that finds gcd of two numbers, then you are almost done:

int gcd (int a, int b);

int gcd3 (int a, int b, int c)

{

return gcd (gcd (a, b), c);

}

Answer 3

The HCF (highest common factor) is better known as the GCD (greatest common divisor, or greatest common denominator) of two or more factors. That is, the largest value that will evenly divide all the factors. The LCM is the lowest common multiple of the factors. To efficiently obtain the LCM of two or more factors you first need to know the GCD of those same factors, such that LCM(a,b) is computed as a/GCD(a,b)*b.

The GCD computation is a naturally recursive operation. But while the recursive approach is elegent, an iterative approach will yield results more efficiently. The following example uses the iterative approach, but the recursive version of the GCD function is included so you may compare.

In its basic form, the GCD can be computed for any two positive integers. The result of this computation can then be used to cumulatively determine the GCD of three or more integers. An overload is provided to specifically handle 3 integers, however to handle more than 3 integers, place the integers in an array and call grc_arr() instead, passing the array by reference along with its size.

The following example demonstrates both GCD and LCM computations, first asserting that the computations work correctly for known values, then randomly testing arrays of 3 to 5 random integers.

#include<assert.h>

#include<iostream>

#include<time.h>

// Returns the greatest common divisor of the given positive integers (iterative method)

unsigned int gcd(unsigned int a, unsigned int b)

{

if(!a)

return(b);

if(!b)

return(a);

int c=0;

while(~(a|b)&1)

{

a>>=1;

b>>=1;

++c;

}

while(~a&1)

a>>=1;

do{

while(~b&1)

b>>=1;

if(a>b)

a^=b^=a^=b;

b-=a;

}while(b);

return(a<<c);

}

// Returns the greatest common divisor of the given positive integers.

unsigned int gcd(unsigned int a, unsigned int b, unsigned int c)

{

return(gcd(gcd(a,b),c));

}

// Returns the greatest common divisor in the given array.

unsigned int gcd_arr(unsigned int n[], unsigned int size)

{

switch(size)

{

case(0): return(0);

case(1): return(n[0]);

case(2): return(gcd(n[0],n[1]));

}

--size;

return(gcd(gcd_arr(n,size),n[size]));

}

void gcd_invariants()

{

assert( gcd(0,0) == 0 );

assert( gcd(0,1) == 1 );

assert( gcd(2,4) == 2 );

assert( gcd(6,9) == 3 );

assert( gcd(21,84) == 21 );

assert( gcd(60,12,4) == 4 );

unsigned int n[5]={16,32,64,48,8};

assert( gcd_arr(n,5) == 8 );

}

// Returns the lowest common multiple of the two given integers.

unsigned int lcm(unsigned int a, unsigned int b)

{

if(!a!b)

return(0);

return(a/gcd(a,b)*b);

}

// Returns the lowest common multiple of the three given integers.

unsigned int lcm(unsigned int a, unsigned int b, unsigned int c)

{

return(lcm(lcm(a,b),c));

}

// Returns the lowest common multiple of the given array.

unsigned int lcm_arr(const unsigned int n[], unsigned int size)

{

switch(size)

{

case(0): return(0);

case(1): return(n[0]);

case(2): return(lcm(n[0],n[1]));

}

--size;

return(lcm(lcm_arr(n,size),n[size]));

}

void lcm_invariants()

{

assert( lcm(0,0) == 0 );

assert( lcm(3,4) == 12 );

assert( lcm(3,4,5) == 60 );

assert( lcm(4,5,6) == 60 );

unsigned int n[5] = {2,3,4,5,6};

assert( lcm_arr(n,5)==60 );

}

int main()

{

using std::cout;

using std::endl;

gcd_invariants();

lcm_invariants();

// Exercise random arrays of size 3 to 5.

srand((unsigned) time(NULL));

for(unsigned int attempt=0; attempt<10; ++attempt)

{

unsigned int size=rand()%3+3;

unsigned int* num = new unsigned int[size];

unsigned int index=0;

while(index<size)

num[index++]=rand()%100;

unsigned int hcf=gcd_arr(num,size);

cout<<"GCD(";

index=0;

cout<<num[index];

while(++index<size)

cout<<','<<num[index];

cout<<") = "<<hcf<<endl;

unsigned int lcm=lcm_arr(num,size);

cout<<"LCM(";

index=0;

cout<<num[index];

while(++index<size)

cout<<','<<num[index];

cout<<") = "<<lcm<<endl;

delete[]num;

}

}

The following function is not part of the example, but demonstrates the recursive approach to computing the GCD. Replace the GCD function in the example above to make use of it. You can use high-performance timers to compare its performance with the iterative approach but you must comment out the srand() function call to ensure the results are consistent.

// Returns the greatest common divisor of the given positive integers (recursive method).

unsigned int gcd(unsigned int a, unsigned int b)

{

if(!a)

return(b);

if(!b)

return(a);

if(~a&1)

{

if(b&1)

return(gcd(a>>1,b));

else

return(gcd(a>>1,b>>1)<<1);

}

if(~b&1)

return(gcd(a,b>>1));

if(a>b)

return(gcd((a-b)>>1,b));

return(gcd((b-a)>>1,a));

}

Answer 4

To find the least common multiple (LCM) of any two non-zero positive numbers you first need to determine the greatest common divisor (GCD) of those numbers, such that LCM(a,b) == (a*b) / GCD(a,b)

The GCD for any two values can be determined by repeatedly subtracting the lowest value from the largest value until both values are the same.

The following program will generate 10 pairs of values at random and print their LCM and GCD values.

#include<iostream>

#include<iomanip>

#include<random>

#include<ctime>

unsigned greatest_common_divisor (unsigned a, unsigned b)

{

while (a!=b)

a>b?a-=b:b-=a;

return a;

}

unsigned lowest_common_multiple (const unsigned a, const unsigned b)

{

return (a*b)/greatest_common_divisor (a,b);

}

int main()

{

std::default_random_engine generator ((unsigned)time(0));

std::uniform_int_distribution<int> distribution (10,99);

for (unsigned loop=0; loop<10; ++loop)

{

const unsigned a = distribution (generator);

const unsigned b = distribution (generator);

const unsigned gcd = greatest_common_divisor (a, b);

const unsigned lcm = lowest_common_multiple (a, b);

std::cout << a << " and " << b

<< " LCM: " << std::setw(4) << lcm

<< " GCD: " << std::setw(4) << gcd

<< std::endl;

}

}

Answer 5

HCF (highest common factor), GCF (greatest common factor) and GCD (greatest common divisor) all mean the same thing: the largest value that evenly divides two or more values.

The following C++ implementation includes both the recursive method and the iterative method, utilising the recursive method by default. To use the iterative method, comment out the #define RECURSIVE line.

#include<iostream>

#include<time.h>

#define RECURSIVE // comment out to use iterative method

#ifdef RECURSIVE

// Returns the GCD of the two given integers (recursive method)

unsigned int gcd(unsigned int a, unsigned int b)

{

if(!a)

return(b);

if(!b)

return(a);

if(a==b)

return(a);

if(~a&1)

{

if(b&1)

return(gcd(a>>1,b));

else

return(gcd(a>>1,b>>1)<<1);

}

if(~b&1)

return(gcd(a,b>>1));

if(a>b)

return(gcd((a-b)>>1,b));

return(gcd((b-a)>>1,a));

}

#else

// Returns the GCD of the two given integers (iterative method)

unsigned int gcd(unsigned int a, unsigned int b)

{

if(!a)

return(b);

if(!b)

return(a);

int c;

for(c=0; ((a|b)&1)==0; ++c)

{

a>>=1;

b>>=1;

}

while((a&1)==0)

a>>=1;

do{

while((b&1)==0)

b>>=1;

if(a>b)

{

unsigned int t=a;

a=b;

b=t;

}

b-=a;

}while(b);

return(a<<c);

}

#endif RECURSIVE

int main()

{

using std::cout;

using std::endl;

srand((unsigned) time(NULL));

for(unsigned int attempt=0; attempt<10; ++attempt)

{

unsigned int x=rand()%100;

unsigned int y=rand()%100;

unsigned int hcf=gcd(x,y);

cout<<"GCD("<<x<<','<<y<<") = "<<hcf<<endl;

}

cout<<endl;

}

Answer 6

#include<assert.h>

#include<iostream>

#include<time.h>

#include<Windows.h>

// Returns the greatest common divisor of the given positive integers (recursive method).

unsigned int gcd(unsigned int a, unsigned int b)

{

if(!a)

return(b);

if(!b)

return(a);

if(~a&1)

{

if(b&1)

return(gcd(a>>1,b));

else

return(gcd(a>>1,b>>1)<<1);

}

if(~b&1)

return(gcd(a,b>>1));

if(a>b)

return(gcd((a-b)>>1,b));

return(gcd((b-a)>>1,a));

}

// Returns the greatest common divisor of the given positive integers.

unsigned int gcd(unsigned int a, unsigned int b, unsigned int c)

{

return(gcd(gcd(a,b),c));

}

// Returns the greatest common divisor in the given array.

unsigned int gcd_arr(unsigned int n[], unsigned int size)

{

switch(size)

{

case(0): return(0);

case(1): return(n[0]);

case(2): return(gcd(n[0],n[1]));

}

--size;

return(gcd(gcd_arr(n,size),n[size]));

}

void gcd_invariants()

{

assert( gcd(0,0) 60 );

unsigned int n[5] = {2,3,4,5,6};

assert( lcm_arr(n,5)==60 );

}

int main()

{

using std::cout;

using std::endl;

gcd_invariants();

lcm_invariants();

// Exercise random arrays of size 3 to 5.

//srand((unsigned) time(NULL));

for(unsigned int attempt=0; attempt<10; ++attempt)

{

unsigned int size=rand()%3+3;

unsigned int* num = new unsigned int[size];

unsigned int index=0;

while(index<size)

num[index++]=rand()%100;

unsigned int hcf=gcd_arr(num,size);

cout<<"GCD(";

index=0;

cout<<num[index];

while(++index<size)

cout<<','<<num[index];

cout<<") = "<<hcf<<endl;

unsigned int lcm=lcm_arr(num,size);

cout<<"LCM(";

index=0;

cout<<num[index];

while(++index<size)

cout<<','<<num[index];

cout<<") = "<<lcm<<endl;

delete[]num;

}

}

Answer 7

The GCF (Greatest Common Factor) of two or more numbers is the largest factor shared by those numbers. A factor of a number is an integer (not a floating point) that can be evenly divided by a larger number - the division must produce an integer and not a floating point.

The first step in your algorithm is to collect all of the factors for each number into separate arrays.

Factoring a number is as simple as using a for() loop to count "c" from 1 to half of the target number (n). Then take the modulus value of n%c - if it's 0, then c is a factor of n. Store it in the array.

Once you have the arrays initialized, loop from the last value in the array to the first and see if that value appears in the other arrays. If it does, you've found your GCF. Since "1" is guaranteed to be a common factor in all arrays, and you've stored 1 in all arrays, your loop will return a value, but it's a good idea to return -1 after the loop. If an error occurs within your code, -1 is returned, and you know you have to debug it to get it working properly.

Answer 8

Given two numbers, a and b, you can find their lowest common multiple (lcm) by calling the standard library lcm function:

auto x = std::lcm (a, b);