# algorithm for common divisor

• Sep 17th 2009, 06:12 AM
Julius
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? :)
• Sep 20th 2009, 03:40 AM
davidlyness
PROGRAM divisor;

VAR

BEGIN

END.

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

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.
• Sep 20th 2009, 05:00 PM
aidan
Quote:

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:

\$\displaystyle a = kp_1 \$
\$\displaystyle b = kp_2 \$
\$\displaystyle c = kp_3\$

r = a+b+c

' \$\displaystyle 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.
• Sep 24th 2009, 05:36 AM
Julius
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...