Given a rectangle of sides $m$ and $n$. $( m,n \in [1,1000] )$ We can cut the rectangle into smaller identical pieces such that each piece is a square having maximum possible side length with no left over piece of the rectangle. How could we count this squares of maximum size?
For example: If the rectangle is of size $6 \times 9$. We can cut it into 54 squares of size $1 \times 1$, $0$ of size $2 \times 2$, $6$ of size $3 \times 3$, $0$ of size $4 \times 4$, $0$ of size $5 \times 5$ and $0$ of size $6 \times 6$. The minimum number of squares of maximum size that can cut is $6$.
My approach: I computed the product $m \times n$ say $K$.Then found the maximum perfect square that divides $K$. The quotient of this division seems to be the required answer. But unfortunately it's doesn't seem to yield correct answer. Where exactly I am going wrong?