The square plots

Problem

Don Aniceto, the surveyor of the valley, was asked to split a piece of land of width by height rods into square plots, all the same size and laid out in even rows and columns. The plots are not cut and not turned: the strip left over at the edge stays as a boundary, unshared, and belongs to nobody. The owner asked for at least wanted plots, and don Aniceto wants them as big as he can, because a small plot is not worth sowing.

Write a function that takes width, height and wanted (all three from 1 up) and returns the biggest side, in whole rods, that still gives wanted plots or more. If not even a side of 1 is enough, you return 0.

With a piece of land 10 by 9 rods and 4 plots asked for, the side is 4: two plots fit across the width and two along the height, so 4, and the boundary left over is a strip of 2 rods on one side and 1 rod on the other. With a side of 5 only two plots would fit, so 4 is the biggest one that works.

With a piece of land 100 by 60 and 7 plots asked for, the side is 25: 4 plots fit across the width and 2 along the height, so 8.

With a fixed side, how many plots fit across the width and how many along the height are two whole divisions. And notice something: the bigger the side, the fewer plots come out, never more. That order is what lets you split the range of sides in half instead of trying them all.

width, height and wanted go up to a billion, so trying side by side never ends. And watch out for the size of the numbers: on a piece of land a billion by a billion, a side of 1 gives a quintillion plots, and a number like that no longer fits exactly in JavaScript. Look closely at what you compare against, so you never have to go that far.

Examples

• The one from the example

  10, 9, 4 → 4

• A hundred by sixty

  100, 60, 7 → 25

• Not even a side of 1 is enough

  3, 3, 10 → 0

• One single plot, the whole land

  1000000000, 1000000000, 1 → 1000000000

• The land that is one rod high

  1000, 1, 3 → 1

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def side(width, height, wanted):
    pass

function side(width, height, wanted) {
}