# Calculating lcm and gcd...

I wrote a program a little while ago that can calculate lcm and gcd of natural numbers. But its slow, to calculate the lcm of 123 345 567, it took 33 seconds. Anybody who can write a code which can perform faster. Thanx in advance.

• : I wrote a program a little while ago that can calculate lcm and gcd of natural numbers. But its slow, to calculate the lcm of 123 345 567, it took 33 seconds. Anybody who can write a code which can perform faster. Thanx in advance.
:
What is lcm and gcd ?
• : : I wrote a program a little while ago that can calculate lcm and gcd of natural numbers. But its slow, to calculate the lcm of 123 345 567, it took 33 seconds. Anybody who can write a code which can perform faster. Thanx in advance.
: :
: What is lcm and gcd ?
:

Least Common Multiple - Smallest number that all given numbers can be evenly multiplied into. 2, 3 and 4 = 12 (2*6, 3*4 and 4*3).

Greatest Common Denominator - Largest number that can be evenly divided into all the given numbers. 6, 12 and 15 = 3 (3*2, 3*4 and 3*5).

I could come up with something, but it'd probably be the slowest code anyone has ever seen.
• [b][red]This message was edited by the PrzemekG_ at 2002-5-27 15:15:49[/red][/b][hr]
: : : I wrote a program a little while ago that can calculate lcm and gcd of natural numbers. But its slow, to calculate the lcm of 123 345 567, it took 33 seconds. Anybody who can write a code which can perform faster. Thanx in advance.
: : :
: : What is lcm and gcd ?
: :
:
: Least Common Multiple - Smallest number that all given numbers can be evenly multiplied into. 2, 3 and 4 = 12 (2*6, 3*4 and 4*3).
:
: Greatest Common Denominator - Largest number that can be evenly divided into all the given numbers. 6, 12 and 15 = 3 (3*2, 3*4 and 3*5).
:
: I could come up with something, but it'd probably be the slowest code anyone has ever seen.
:

Ohhh, sorry, I hate that kind of problems, anyways why do you need it ?

PS. You could give your code, maybe there are some opimalizations to do
• : [b][red]This message was edited by the PrzemekG_ at 2002-5-27 15:15:49[/red][/b][hr]
: : : : I wrote a program a little while ago that can calculate lcm and gcd of natural numbers. But its slow, to calculate the lcm of 123 345 567, it took 33 seconds. Anybody who can write a code which can perform faster. Thanx in advance.
: : : :
: : : What is lcm and gcd ?
: : :
: :
: : Least Common Multiple - Smallest number that all given numbers can be evenly multiplied into. 2, 3 and 4 = 12 (2*6, 3*4 and 4*3).
: :
: : Greatest Common Denominator - Largest number that can be evenly divided into all the given numbers. 6, 12 and 15 = 3 (3*2, 3*4 and 3*5).
: :
: : I could come up with something, but it'd probably be the slowest code anyone has ever seen.
: :
:
: Ohhh, sorry, I hate that kind of problems, anyways why do you need it ?
:
: PS. You could give your code, maybe there are some opimalizations to do
:

I am making a program in which I have a compilation of such stuffs, like Mean finder, Base convertor, Prime number detector, Root finder, Exponent finder etc. I am sorry, I can't give you the code. Because, if I do so, my friend would kill me, as he thinks that CODES are more precious than DIAMONDS.

• : : [b][red]This message was edited by the PrzemekG_ at 2002-5-27 15:15:49[/red][/b][hr]
: : : : : I wrote a program a little while ago that can calculate lcm and gcd of natural numbers. But its slow, to calculate the lcm of 123 345 567, it took 33 seconds. Anybody who can write a code which can perform faster. Thanx in advance.
: : : : :
: : : : What is lcm and gcd ?
: : : :
: : :
: : : Least Common Multiple - Smallest number that all given numbers can be evenly multiplied into. 2, 3 and 4 = 12 (2*6, 3*4 and 4*3).
: : :
: : : Greatest Common Denominator - Largest number that can be evenly divided into all the given numbers. 6, 12 and 15 = 3 (3*2, 3*4 and 3*5).
: : :
: : : I could come up with something, but it'd probably be the slowest code anyone has ever seen.
: : :
: :
: : Ohhh, sorry, I hate that kind of problems, anyways why do you need it ?
: :
: : PS. You could give your code, maybe there are some opimalizations to do
: :
:
: I am making a program in which I have a compilation of such stuffs, like Mean finder, Base convertor, Prime number detector, Root finder, Exponent finder etc. I am sorry, I can't give you the code. Because, if I do so, my friend would kill me, as he thinks that CODES are more precious than DIAMONDS.
:
:

But we are supposed to give up code??? Not a convincing arguement...
• : : [b][red]This message was edited by the PrzemekG_ at 2002-5-27 15:15:49[/red][/b][hr]
: : : : : I wrote a program a little while ago that can calculate lcm and gcd of natural numbers. But its slow, to calculate the lcm of 123 345 567, it took 33 seconds. Anybody who can write a code which can perform faster. Thanx in advance.
: : : : :
: : : : What is lcm and gcd ?
: : : :
: : :
: : : Least Common Multiple - Smallest number that all given numbers can be evenly multiplied into. 2, 3 and 4 = 12 (2*6, 3*4 and 4*3).
: : :
: : : Greatest Common Denominator - Largest number that can be evenly divided into all the given numbers. 6, 12 and 15 = 3 (3*2, 3*4 and 3*5).
: : :
: : : I could come up with something, but it'd probably be the slowest code anyone has ever seen.
: : :
: :
: : Ohhh, sorry, I hate that kind of problems, anyways why do you need it ?
: :
: : PS. You could give your code, maybe there are some opimalizations to do
: :
:
: I am making a program in which I have a compilation of such stuffs, like Mean finder, Base convertor, Prime number detector, Root finder, Exponent finder etc. I am sorry, I can't give you the code. Because, if I do so, my friend would kill me, as he thinks that CODES are more precious than DIAMONDS.
:
: Okay, here is the so called CODE:

'start
PRINT " Please make the following entries..."
entryforlcm:
INPUT "Enter no of digits: ", max
max = FIX(max)
IF max < 0 OR max = 0 THEN COLOR 12: PRINT "!!Invalid Value!!": COLOR 15: GOTO entryforlcm
REDIM numbers(max)
FOR deb = 1 TO max
PRINT " Digit "; : INPUT numbers(deb)
NEXT deb
COLOR 9: PRINT " Press 'Esc' to abort calculation": COLOR 15
COLOR 7: PRINT "The LCM for "; : COLOR 15
FOR I = 1 TO max
PRINT numbers(I);
NEXT I
COLOR 7: PRINT " is"; : COLOR 15
t1 = TIMER
FindLCM numbers(), max, x
t2 = TIMER
PRINT x

'here is the finlcm sub

SUB FindLCM (numbers(), max, x)

x = numbers(1): I = 1

DO
progress = progress + 1
IF INT(x / numbers(I)) = x / numbers(I) THEN
IF I = max THEN
EXIT DO
ELSE
I = I + 1
IF I = max + 1 THEN I = max
END IF
ELSE
x = x + 1: I = 1
END IF

press = INP(&H60)
IF press = 1 THEN COLOR 12: PRINT " !!Calculation Aborted!!": COLOR 15: EXIT DO
LOOP

END SUB

• you could have done this instead:

DEFLNG A-Z
COLOR 9: PRINT "a program to calculate the LOWEST COMMON MULTIPLE of a set of integers"
ON ERROR GOTO handler
COLOR 7: INPUT "How many integers? ", n
: x = 1: FOR n = 1 TO n
: a = x: INPUT "Int: ", b: IF a < b THEN SWAP a, b
: x = a: WHILE x mod b: x = x + a: WEND: NEXT
COLOR 5: PRINT "LCM:"; x: END
handler: PRINT "Result too large": END