Paper Cut into Minimum Number of Squares

Given a paper of size A x B, the task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.


When paper size is 36 x 30, the output should be 5. An 36 x 30 paper can be cut into 3 squares of size 12 x 12 and 2 squares of size 18 x 1.

Please note that greedy approach doesn't always work. For example in the above example, greedy solution is 6, 1 square of size 30 x 30 and 5 squares of size 6 x 6.

Contributed by Berkan Teber