# LCM and GCD of two numbers.

Page 1 of 1

## 5 Replies - 28664 Views - Last Post: 01 July 2008 - 11:30 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=56223&amp;s=964933c28ae98b4df0a1039fe06ed7de&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #4 arundavid.info

Reputation: 2
• Posts: 3
• Joined: 23-May 08

## Re: LCM and GCD of two numbers.

Posted 29 June 2008 - 08:58 PM

Is that any other fast way to find L.C.M and G.C.D of two numbers.
If you know,Plz send me dat..........
```#include"iostream.h"
#include"conio.h"
void main()
{
int a,b,g;clrscr();
cin>>a>>b;
if(a<b) g=a;
else g=b;
for(;;g--)
if(a%g==0&&b%g==0)
{
cout<<"\nG.C.D:"<<g;
break;
}
cout<<"\nL.C.M:"<<a*b/g;
getch();
}

```

This post has been edited by arundavid.info: 29 June 2008 - 09:01 PM

### #5 thompson03

Reputation: 1
• Posts: 23
• Joined: 12-June 08

## Re: LCM and GCD of two numbers.

Posted 29 June 2008 - 11:52 PM

I would think it would depend on the size of the numbers.

You code is "short", but if a and b were very very large numbers,
you could cut down on the loop time by factoring them using one of the following...

the square root of the number your factoring is the largest posible factor of that number,
so if the number was 10 digits, could cut your loop time down consiberably by factoring each number and comparing their factors.

even faster would be to factor using a list of prime numbers,

ex. to factor a larger number like 10000000000, you need only look at (x=2;x<=100,000;x--)

ex. if you had the prime number list up to 10,000 stored in a p[ ] variable, then (x=0; x <=1240; x--) where p[x] would give the list of prime factors less than 10000

not sure if this is where you wanted to go with with this.

Will be happy to talk more tomorrow if not, Bed time now.

### #6 polymath

Reputation: 52
• Posts: 670
• Joined: 04-April 08

## Re: LCM and GCD of two numbers.

Posted 30 June 2008 - 08:11 AM

Use euclids algorithm.

### #7 arundavid.info

Reputation: 2
• Posts: 3
• Joined: 23-May 08

## Re: LCM and GCD of two numbers.

Posted 01 July 2008 - 01:46 AM

```
```

This post has been edited by arundavid.info: 01 July 2008 - 01:49 AM

### #8 polymath

Reputation: 52
• Posts: 670
• Joined: 04-April 08

## Re: LCM and GCD of two numbers.

Posted 01 July 2008 - 07:38 AM

?

### #9 captainhampton

• Jawsome++;

Reputation: 14
• Posts: 548
• Joined: 17-October 07

## Re: LCM and GCD of two numbers.

Posted 01 July 2008 - 11:30 AM

As polymath says, use Euclid's algorithm which if you need help, follow this link:
http://en.wikipedia....idean_algorithm
Plenty of pseudo-code information for you to get started.