Results 1 to 4 of 4

Math Help - algorithm for common divisor

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    24

    algorithm for common divisor

    dont know if im writing in right section, but heres the problem: i have to write a program to find at least one common divisor of 3 numbers.. the problem is, that its not allowed to use while,for,functions and procedures (pascal language is needed). so only if,else,mod... my last try was
    procedure cd(a,b,c,d) {
    if((a mod d = 0) and (b mod d = 0) and......)
    ....
    else
    cd(a,b,c,d+1)
    }
    but like i said, procedures seems to be not allowed.. so is there any possible solution?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2009
    From
    United Kingdom
    Posts
    9
    PROGRAM divisor;

    VAR
    answer : INTEGER;

    BEGIN

    answer := 1;
    write(answer);

    END.

    (Although I think your tutor might be looking for a bit more than that. )

    On a more serious note, I don't think there's any way to do it without using either iteration (while / for) or recursion (procedures with parameters). Let me know if you do find a solution.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by Julius View Post
    dont know if im writing in right section, but heres the problem: i have to write a program to find at least one common divisor of 3 numbers.. the problem is, that its not allowed to use while,for,functions and procedures (pascal language is needed). so only if,else,mod... my last try was
    procedure cd(a,b,c,d) {
    if((a mod d = 0) and (b mod d = 0) and......)
    ....
    else
    cd(a,b,c,d+1)
    }
    but like i said, procedures seems to be not allowed.. so is there any possible solution?

    If makes little sense not to use a loop. The language was designed to use loops: for/next, while/wend, repeat/until ... etc

    This will work
    Given three numbers with a common divisor:

     a = kp_1
     b = kp_2
     c = kp_3

    r = a+b+c

    '  r = k(p_1 + p_2 + p_3) )

    s = a
    ' or s = b or s = c, your choice

    'you will need to have these statements until it exits
    r = r mod s
    if r = 0 then divisor = s : exit
    s = s mod r
    if s = 0 then divisor = r : exit

    'again
    r = r mod s
    if r = 0 then divisor = s : exit
    s = s mod r
    if s = 0 then divisor = r : exit

    'again
    r = r mod s
    if r = 0 then divisor = s : exit
    s = s mod r
    if s = 0 then divisor = r : exit

    'again
    r = r mod s
    if r = 0 then divisor = s : exit
    s = s mod r
    if s = 0 then divisor = r : exit

    'again
    r = r mod s
    if r = 0 then divisor = s : exit
    s = s mod r
    if s = 0 then divisor = r : exit

    ....
    You may need to repeat these a few more times or a few hundred times.
    It depends on the structure of the numbers
    '& etc
    ...
    r = r mod s
    if r = 0 then divisor = s : exit
    s = s mod r
    if s = 0 then divisor = r : exit
    ...
    ;
    at some point the routine WILL EXIT.

    Could you explain why a simple loop is forbidden?

    With some numbers you can find a common divisior in a single step.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2009
    Posts
    24
    everything is ok now, my tutor accepted program with recursion. he doesnt allow to use some functions as to make it harder to write programs...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 06:45 AM
  2. Common Divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 6th 2010, 12:05 PM
  3. Greastest Common Divisor
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 9th 2009, 02:24 AM
  4. Replies: 0
    Last Post: September 14th 2009, 02:08 AM
  5. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2009, 08:16 PM

Search Tags


/mathhelpforum @mathhelpforum