LCM and GCD of two numbers.

To find LCM and GCD of two numbers.

Page 1 of 1

5 Replies - 26244 Views - Last Post: 01 July 2008 - 11:30 AM Rate Topic: -----

#4 arundavid.info  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • 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

Was This Post Helpful? 1

#5 thompson03  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • 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.
Was This Post Helpful? 1

#6 polymath  Icon User is offline

  • D.I.C Addict
  • member icon

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

Re: LCM and GCD of two numbers.

Posted 30 June 2008 - 08:11 AM

Use euclids algorithm.
Was This Post Helpful? 1
  • +
  • -

#7 arundavid.info  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#8 polymath  Icon User is offline

  • D.I.C Addict
  • member icon

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

Re: LCM and GCD of two numbers.

Posted 01 July 2008 - 07:38 AM

?
Was This Post Helpful? 0
  • +
  • -

#9 captainhampton  Icon User is offline

  • Jawsome++;
  • member icon

Reputation: 13
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1