Nearly-Square Divisors

August 5, 2016

We have today a fun little problem from number theory:

Given positive integers n, a and b such that n = a · b with ab, find a and b such that the difference ab is as small as possible.

For n square, the solution is just the square root of n; for instance, with n = 36, a = b = 6. Otherwise, a and b will be the two divisors nearest the square root; for instance, with n = 60, a = 10 and b = 6.

Your task is to write a program to find a and b as described above; use your program to find the nearly square divisors of n = 224403121196654400. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2