- #1
flying2000
- 40
- 0
algorithm to prove lcm:
a:=m
b:=n
while a != b
if a < b
a:= a + m
else
b:= b + n
//postcondition: a is the lcm(m,n)
what's the loop invariant?I thought it is(not sure):
lcm(ak, bk) = lcm(ak/m, bk/n) *lcm(m,n)
I am not sure and also impossible to prove my loop invariant...
Another loop invariant I thought is "ak=qm and bk=rn",but I don't know how to
show it's the lcm of m and n,
Thanks in advance!
a:=m
b:=n
while a != b
if a < b
a:= a + m
else
b:= b + n
//postcondition: a is the lcm(m,n)
what's the loop invariant?I thought it is(not sure):
lcm(ak, bk) = lcm(ak/m, bk/n) *lcm(m,n)
I am not sure and also impossible to prove my loop invariant...
Another loop invariant I thought is "ak=qm and bk=rn",but I don't know how to
show it's the lcm of m and n,
Thanks in advance!