# Finding LCM & GCD in C

Discussion in 'C' started by pradeep, Oct 5, 2005.

Tags:

Joined:
Apr 4, 2005
Messages:
1,645
87
Trophy Points:
0
Occupation:
Programmer
Location:
Kolkata, India
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;
}
}```

Last edited: Oct 5, 2005

Joined:
Jul 12, 2004
Messages:
15,374
388
Trophy Points:
83
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;
}
}```

3. ### SATYAN JANANew Member

Joined:
Jul 31, 2004
Messages:
7
0
Trophy Points:
0
Occupation:
Programming
Location:
Kolkata
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.

Joined:
Apr 4, 2005
Messages:
1,645
87
Trophy Points:
0
Occupation:
Programmer
Location:
Kolkata, India
Right said Satyan, even I was about to post the same.

Thanks Shabbir for the modified code for the loop.

Joined:
Jul 12, 2004
Messages:
15,374
388
Trophy Points:
83
Yup realized that.

Joined:
Apr 4, 2005
Messages:
1,645
87
Trophy Points:
0
Occupation:
Programmer
Location:
Kolkata, India
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```

7. ### BlasterBlangNew Member

Joined:
Nov 13, 2006
Messages:
10
0
Trophy Points:
0
thanks buddy.....this might short'n my calcutaion

Last edited by a moderator: Nov 14, 2006

Joined:
Jul 12, 2004
Messages:
15,374
388
Trophy Points:
83
BlasterBlang, this is the third time I have been telling you to confine links to signatures only.

9. ### BlasterBlangNew Member

Joined:
Nov 13, 2006
Messages:
10
0
Trophy Points:
0
ok...fine

10. ### BlasterBlangNew Member

Joined:
Nov 13, 2006
Messages:
10
0
Trophy Points:
0
but link are not enable in signatures

Joined:
Jul 12, 2004
Messages:
15,374
388
Trophy Points:
83
They will appear once on a page. You will see it on the seventh post of the thread.

12. ### insamdNew Member

Joined:
Dec 18, 2006
Messages:
1
0
Trophy Points:
0
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

13. ### BlasterBlangNew Member

Joined:
Nov 13, 2006
Messages:
10
0
Trophy Points:
0
helloo

14. ### sharma_atul13New Member

Joined:
Jul 16, 2007
Messages:
7
0
Trophy Points:
0
liked the way to do manipulations done in LCM and GCD programs

15. ### clockingNew Member

Joined:
Jun 12, 2007
Messages:
122
0
Trophy Points:
0
hi everyone!
I have code following:
You see and shift it
Code:
```struct ths
{
char ht;
char tt;
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.

Last edited by a moderator: Jul 22, 2007

Joined:
Jul 12, 2004
Messages:
15,374
388
Trophy Points:
83
[COMMENT]Use code tag ([ code][/code ]) when you have code snippets in the post.[/COMMENT]

17. ### clockingNew Member

Joined:
Jun 12, 2007
Messages:
122
0
Trophy Points:
0 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?

18. ### clockingNew Member

Joined:
Jun 12, 2007
Messages:
122
0
Trophy Points:
0
hi everybody!
Follow you, Can we do in swap 2 structs easier?
Code:
```tmp = ts[i] ;
ts[i] = ts[j];
ts[j] = tmp;
```
thanks.

Joined:
Jul 12, 2004
Messages:
15,374
388
Trophy Points:
83
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.

Joined:
Jun 12, 2007
Messages:
122