Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   Finding LCM & GCD in C (http://www.go4expert.com/articles/finding-lcm-gcd-c-t457/)

pradeep 6Oct2005 01:18

Finding LCM & GCD in C
 
Two of my friends faced a problem with writing a program which finds the LCM(Lowest Common Multiple)/GCD(Greatest Common Divisor) of two positive integers, so I helped them out by writing two functions for each. I thought many others might be having the same problem.
So here are the functions:

For LCM:
Code:

/* a & b are the numbers whose LCM is to be found */
  int lcm(int a,int b)
  {
    int n;
    for(n=1;;n++)
    {
          if(n%a == 0 && n%b == 0)
            return n;
    }
  }

For GCD:
Code:

/* a & b are the numbers whose GCD is to be found.
 Given a > b
 */
  int gcd(int a,int b)
  {
    int c;
    while(1)
    {
          c = a%b;
          if(c==0)
            return b;
          a = b;
          b = c;
    }
  }


shabbir 6Oct2005 03:51

Re: Finding LCM & GCD in C
 
For LCM
Code:

if(n%a == 0 && n%b == 0)
shouldn't this be
Code:

if(a%n == 0 && b%n == 0)
Also just another way to write the loop
Code:

    for(n=1;;n++)
    {
          if(n%a == 0 && n%b == 0)
            return n;
    }

can be
Code:

for(n=1;a%n == 0 && b%n == 0;n++);
return n

For GCD Given a > b can be avoided if we have the following code
Code:

  int gcd(int a,int b)
  {
    int c;
    if(a<b)
    {
        c = a;
        a = b;
        b = c;
    }
    while(1)
    {
          c = a%b;
          if(c==0)
            return b;
          a = b;
          b = c;
    }
  }


SATYAN JANA 6Oct2005 12:55

Re: Finding LCM & GCD in C
 
Shabbir,
Least Common Multiple(L.C.M.) of 'a' and 'b' is the smallest number 'n' which is both perfectly divisible by 'a' as well as 'b'; i.e. n%a == 0 && n%b == 0.

pradeep 6Oct2005 13:34

Re: Finding LCM & GCD in C
 
Right said Satyan, even I was about to post the same.

Thanks Shabbir for the modified code for the loop.

shabbir 6Oct2005 13:55

Re: Finding LCM & GCD in C
 
Quote:

Originally Posted by SATYAN JANA
Shabbir,
Least Common Multiple(L.C.M.) of 'a' and 'b' is the smallest number 'n' which is both perfectly divisible by 'a' as well as 'b'; i.e. n%a == 0 && n%b == 0.

Yup realized that.

pradeep 7Oct2005 11:08

Re: Finding LCM & GCD in C
 
Quote:

Also just another way to write the loop
Code:
for(n=1;;n++)
{
if(n%a == 0 && n%b == 0)
return n;
}

can be
Code:
for(n=1;a%n == 0 && b%n == 0;n++);
return n

This loop won't work, the condition given would prevent the execution even once.
The correct code would be:
Code:

  for(n=1;n%a != 0 && n%b != 0;n++);
  return n


BlasterBlang 14Nov2006 17:55

Re: Finding LCM & GCD in C
 
thanks buddy.....this might short'n my calcutaion

shabbir 14Nov2006 18:17

Re: Finding LCM & GCD in C
 
BlasterBlang, this is the third time I have been telling you to confine links to signatures only.

BlasterBlang 17Nov2006 16:43

Re: Finding LCM & GCD in C
 
ok...fine

BlasterBlang 17Nov2006 16:45

Re: Finding LCM & GCD in C
 
but link are not enable in signatures

shabbir 17Nov2006 18:24

Re: Finding LCM & GCD in C
 
They will appear once on a page. You will see it on the seventh post of the thread.

insamd 18Dec2006 10:14

Re: Finding LCM & GCD in C
 
hey guys,

Was just interested if with the GCD function if its possible to find the GCD of 3 different numbers rather than just 2? Would be interested to see it.

Thanks

BlasterBlang 27Dec2006 13:13

Re: Finding LCM & GCD in C
 
helloo

sharma_atul13 17Jul2007 13:59

Re: Finding LCM & GCD in C
 
liked the way to do manipulations done in LCM and GCD programs

clocking 22Jul2007 15:03

Re: Finding LCM & GCD in C
 
hi everyone!
I have code following:
You see and shift it
Code:

struct ths
{
  char ht[24];
  char tt[21];
  int sobd;
  float m,l,;
};
class ts
{
  private:
    int sots;
    ths *ts;
  public:
  ts()
  {
    sots = 0 ;
    ts = NULL;
  }
void swap();
};

void ts::swap()
{
  int n = sots;
  for ( int i = 1; i < n; ++i)
  for (int j = i + 1; j <= n; ++j)
  if (ts[i].m < ts[j].m)
  {
    ths tmp = ts[i];
    ts[i] = ts[j];
    ts[j] = tg;
  }
}

// thanks.

shabbir 22Jul2007 20:00

Re: Finding LCM & GCD in C
 
Offtopic comment:
Use code tag ([ code][/code ]) when you have code snippets in the post.

clocking 23Jul2007 07:10

Re: Finding LCM & GCD in C
 
Quote:

Originally Posted by shabbir
Offtopic comment:
Use code tag ([ code][/code ]) when you have code snippets in the post.

:) Thanks so much, my friend!
this is code in C++, how do you see ?
ofcourse, Class in C++ is difficult.
What way do you help me to express easy?

clocking 23Jul2007 07:15

Re: Finding LCM & GCD in C
 
hi everybody!
Follow you, Can we do in swap 2 structs easier?
Code:

tmp = ts[i] ;
ts[i] = ts[j];
ts[j] = tmp;

thanks.

shabbir 23Jul2007 08:28

Re: Finding LCM & GCD in C
 
You can swap the struct if they are addresses and not the objects can be done in that way unless they have the overloaded = operator.

clocking 23Jul2007 12:49

Re: Finding LCM & GCD in C
 
thank, but can we do easier for it ?
not tmp.

oleber 23Jul2007 18:33

Re: Finding LCM & GCD in C
 
Lets see the performance.

:confused: Which is the fastest algorithm?

:) GCM seems to be at most n
:( LCM seems to be at most n*m

:p so, if you do lcm(a,b) := (a*b)/gcm(a,b), you get a n complexity

:eek: This is mathematics.

oleber 24Jul2007 13:50

Re: Finding LCM & GCD in C
 
Swamp is the subject of another post:
http://www.go4expert.com/showthread.php?t=1732

shabbir 24Jul2007 14:17

Re: Finding LCM & GCD in C
 
Quote:

Originally Posted by oleber
Swamp is the subject of another post:
http://www.go4expert.com/showthread.php?t=1732

Could not get what you meant here.

oleber 24Jul2007 14:26

Re: Finding LCM & GCD in C
 
clocking and shabbir are speaking of swaping variables.

This subject was already spoken in the other thread. Just that

clocking 24Jul2007 19:11

Re: Finding LCM & GCD in C
 
:) hi !
thanks for your idea. But I only want someone tell me about that algorithm.
Swapping is not difficult, but I'm interested in the easier way solving it.
Code:

tmp = ts[i];
ts[i] = ts[j];
ts[j] = tmp;

can't we use tmp ?

Balaselvi 27Feb2008 10:13

Re: Finding LCM & GCD in C
 
Hi,

This is Bala.
I want to know how to calculate GCD of many numbers, ex 2048 values.

Please help.

Thanks in advance.

asadullah.ansari 27Feb2008 12:24

Re: Finding LCM & GCD in C
 
Code:

int main()
{
    int n1,n2,n3,n;
    cout<<" Numbers are : ";
    cin>>n1>>n2>>n3;
    n=FindGcd(FindGcd(n1,n2),n3);
    cout<<"GCD of n1,n2,and n3 is "<<n<<endl;
    return 0;
}

int FindGcd(int num1, int num2)
{
    int temp;   
    while(num2!=0)
    {
        temp = num2;
        num2 = num1%num2;
        num1 = temp;
    }   
    return num1;
}


aisha.ansari84 5Mar2008 18:22

Re: Finding LCM & GCD in C
 
can you please tell me when the loop will actually stop

zeeme 22Feb2009 20:00

Re: Finding LCM & GCD in C
 
correct code is this 100% checked!

for(n=1;n%a != 0 || n%b != 0;n++);
return n

vanishing_stapler 15May2009 01:55

Re: Finding LCM & GCD in C
 
When I searched for lcm c++, this thread had the top two spots, so I figured that I'd join and put this here.

For finding the LCM (Least Common Multiple) of two integers, a and b, in C++, use:

for(n=a;n%b != 0;n+=a);
return n;

For maximum speed, try to set it up so that the larger number is "a" and the smaller one is "b".

The reasoning:
The least common multiple (LCM) of two numbers, a and b, is the smallest number that is a multiple of "a" AND a multiple of "b". If we already know that the LCM is a multiple of "a", then why not count by "a"? When we count by "a", starting at "a", we are testing every number that is a multiple of "a" already, and only have to see if it is a multiple of "b" too. This code does just that. When "a", the number we're counting by, is larger than 1, the process will be much faster than with those other suggestions, because it's taking bigger steps (at the same speed per step) to get to the same solution.

If "a" is a billion, then this will be at least a billion times faster than this:

for(n=1;n%a != 0 || n%b != 0;n++);
return n;

(even though both work)

I hope this helps.

jackspa 25May2009 12:10

Re: Finding LCM & GCD in C
 
For lcm try this one:
int lcm(int a,int b)
{
int n;
if(a<b)
{
n=a;
a=b;
b=n;
}
for(n=a;n%b!=0;n+=a)
return n;
}:happy:

xpi0t0s 25May2009 14:42

Re: Finding LCM & GCD in C
 
After 8 posts I would have thought you would know about code blocks by now. USE THEM PLEASE.

jackspa 27May2009 15:05

Re: Finding LCM & GCD in C
 
For lcm try this one:
Code:

int lcm(int a;int b)
{
            int n;
            if(a<b)
            {
                        n=a;
                        a=b;
                        b=n;     
            }
            for(n=a;n%b!=0;n+=a)
                  return n;
}

:happy:

jackspa 27May2009 15:10

Re: Finding LCM & GCD in C
 
i had written that function using blocks.i don't know what happened when i posted it.

shabbir 27May2009 19:50

Re: Finding LCM & GCD in C
 
Added that for you now.

jackspa 28May2009 18:57

Re: Finding LCM & GCD in C
 
thank you.

Zaiber 17Dec2009 02:42

Re: Finding LCM & GCD in C
 
Actually, I used the code on the first page to correct my code 'til I got it right. Needed this for a take home exam for C class.

Thanks, and in return I'll give you my code which might help someone.

Code:

int gcd( int x, int y) {
        if ( y == 0 ) {
        return x;
        }
          else if (x%y == 0) {
          return y;
          }
          else {
          return gcd(y,x%y);
          }
          }


COKEDUDE 17Feb2010 05:37

Re: Finding LCM & GCD in C
 
Wouldn't this code also cover both cases of GCD whether your first variable is bigger or your second variable is bigger?

Code:

void gcd(int x, int y)
{
    if (x > y)
    {
        int c;
        while(1)
        {
            c = x % y;
            return y;
            x = y;
            y = c;
        }
    if (y > x)
    {
        int d;
        while(1)
        {
            d = x % y;
            return x;
            y = x;
            x = d;
        }

    }
}


Zaiber 17Feb2010 07:16

Re: Finding LCM & GCD in C
 
Quote:

Originally Posted by COKEDUDE (Post 64358)
Wouldn't this code also cover both cases of GCD whether your first variable is bigger or your second variable is bigger?

Code:

void gcd(int x, int y)
{
    if (x > y)
    {
        int c;
        while(1)
        {
            c = x % y;
            return y;
            x = y;
            y = c;
        }
    if (y > x)
    {
        int d;
        while(1)
        {
            d = x % y;
            return x;
            y = x;
            x = d;
        }

    }
}


Mine worked for both instances ok.

COKEDUDE 17Feb2010 10:04

Re: Finding LCM & GCD in C
 
Quote:

Originally Posted by Zaiber (Post 64359)
Mine worked for both instances ok.

Wow your code is so much simpler and easier to use :). Thx for the code. I'm just stubborn about making up my own stuff sometimes.


All times are GMT +5.5. The time now is 10:47.