# Thread: algorithm for common divisor

1. ## 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?

2. PROGRAM divisor;

VAR

BEGIN

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.

3. Originally Posted by Julius
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.

4. 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...