Calculating lcm and gcd... - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Calculating lcm and gcd...

detjdetj Posts: 16Member
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.

Comments

  • PrzemekG_PrzemekG_ Posts: 595Member
    : 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 ?
  • KDivad LeahcimKDivad Leahcim Posts: 3,948Member
    : : 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.
  • PrzemekG_PrzemekG_ Posts: 595Member
    [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
  • detjdetj Posts: 16Member
    : [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.

  • KDivad LeahcimKDivad Leahcim Posts: 3,948Member
    : : [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...
  • detjdetj Posts: 16Member
    : : [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


  • baobao Posts: 13Member
    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


Sign In or Register to comment.