Archived

This topic is now archived and is closed to further replies.

GCF

This topic is 5534 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Is there a C++ function that finds the GCF of two integers? If so what do I need to #include to use it? Thanks ahead of time.

Share this post


Link to post
Share on other sites
GCF? You mean GCD, greatest common divisor?

It's something like this:
  
// I didn't test this very much...

int gcd(int x, int y)
{
if (x < y) std::swap(x, y);

while (y != 0) {
int t = x%y;
x = y;
y = t;
}
return x;
}
EDIT:
And just for fun, here's some code that forces the compiler to calculate the GCD of two constants. There are no calculations at runtime
  
#define gcd(x, y) (gcd_t<x,y>::value)

template <int x, int y>
struct gcd_t
{
static const int next_x = y;
static const int next_y = x%y;
static const int guard = static_cast<int>(next_y != 0);

static const int value = (guard) ? (gcd_t<next_x*guard, next_y>::value)
: (next_x);
};
template <>
struct gcd_t<0, 0>
{
static const int value = 0;
};


[edited by - Beer Hunter on October 18, 2002 5:17:08 AM]

Share this post


Link to post
Share on other sites