Archived

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

e4

GCF

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