Euclids formula

remainder = function(a, b){
quotient = floor(a/b)
remainder = a - b*quotient
return(remainder)
}
euclid = function(a,b){
while (min(a,b) != 0) {
if (a > b){
a = remainder(a,b)
} else{
b = remainder(a,b)
}
}
return(max(a,b))
}

Im trying to create a function to find the greatest common divisor. can anyone see where i have gone wrong?

There's some annoying switching of arguments you have to do:

euclid = function(a,b){
  while (min(a,b) != 0) {
    if (a > b){
      bnew = remainder(a,b)
      a=b #switch a and b
      b=bnew #update the value for b
    } else{
      anew = remainder(a,b)
      b=a
      a=anew
    }
  }
  return(max(a,b))
}

This was a helpful reference: The Euclidean Algorithm (article) | Khan Academy

You could also try writing a recursive function. I think it would be more succinct.

this only works if a>b so im guessing theres something wrong with the else function

remainder = function(a, b){
quotient = floor(a/b)
remainder = a - b*quotient
return(remainder)
}
euclid = function(a,b){
while (min(a,b) != 0) {
if (a > b){
bnew = remainder(a,b)
a=b
b=bnew
} else{
anew = remainder(b,a)
b=a
a=anew
}
}
return(max(a,b))
}

1 Like

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.

If you have a query related to it or one of the replies, start a new topic and refer back with a link.