How do you find the greatest common factor in c plus plus language?

Answer 1

#include<iostream>

#include<vector>

#include<time.h>

std::vector<unsigned> factors (const unsigned num)

{

std::vector<unsigned> vec;

if (num)

{

for (unsigned f=1; f<num/2; ++f)

if (!(num%f))

vec.push_back (f);

if (num>1)

vec.push_back(num);

}

return (vec);

}

bool exists (unsigned num, std::vector<unsigned>& vec)

{

for (unsigned index=0; index<vec.size(); ++index)

if( num==vec[index] )

return( true );

return( false );

}

std::vector<unsigned> intersection (std::vector<unsigned>& vec1, std::vector<unsigned>& vec2)

{

std::vector<unsigned> intersects;

for (unsigned index=0; index<vec1.size(); ++index)

if (exists (vec1[index], vec2))

intersects.push_back( vec1[index] );

return (intersects);

}

int main()

{

srand ((unsigned) time (NULL));

// repeat 10 times...

unsigned repeat=10;

do{

// select two random numbers (0 to RAND_MAX)

unsigned num1 = (unsigned) rand();

unsigned num2 = (unsigned) rand();

std::vector<unsigned> vec1 = factors (num1);

std::vector<unsigned> vec2 = factors (num2);

std::vector<unsigned> common = intersection (vec1, vec2);

if (common.size())

std::cout<<"The GCF of "<<num1<<" and "<<num2<<" is "<<common.back()<<std::endl;

else

std::cout<<num1<<" and "<<num2<<" have no common factors"<<std::endl;

}while(--repeat);

}

Example output:

The GCF of 20754 and 19236 is 6

The GCF of 29182 and 10926 is 2

The GCF of 29587 and 4089 is 1

The GCF of 9652 and 29485 is 1

The GCF of 12406 and 21097 is 1

The GCF of 15959 and 10156 is 1

The GCF of 15619 and 16111 is 1

The GCF of 4486 and 30240 is 2

The GCF of 17121 and 32223 is 3

The GCF of 30290 and 10534 is 2

Press any key to continue . . .