Nearly-Square Divisors

August 5, 2016

The obvious answer uses brute force to find the divisors one-by-one until reaching the square root:

(define (nsq-div1 n)
  (let loop ((d 1))
    (if (and (zero? (modulo n d))
             (<= n (* d d)))
        (list d (/ n d))
        (loop (+ d 1)))))
> (nsq-div1 36)
(6 6)
> (nsq-div1 60)
(10 6)
> (time (nsq-div1 224403121196654400))
(time (nsq-div1 224403121196654400))
    no collections
    55911 ms elapsed cpu time
    55998 ms elapsed real time
    598016 bytes allocated
(473753280 473670855)

A better answer factors n, computes the divisors as in a previous exercise, then takes the middle two divisors:

(define (factors n)
  (if (even? n) (cons 2 (factors (/ n 2)))
    (let loop ((n n) (f 3) (fs '()))
      (cond ((< n (* f f)) (reverse (cons n fs)))
            ((zero? (modulo n f))
              (loop (/ n f) f (cons f fs)))
            (else (loop n (+ f 2) fs))))))
(define (divisors n)
  (define (times x) (lambda (y) (* x y)))
  (let divs ((fs (factors n)))
    (unique = (sort <
      (if (null? fs) '(1)
        (let ((ds (divs (cdr fs))))
          (append ds (map (times (car fs)) ds))))))))
(define (nsq-div2 n)
  (let* ((divs (divisors n))
         (len (length divs))
         (b (list-ref divs (quotient (- len 1) 2))))
    (list (/ n b) b)))
> (nsq-div2 36)
(6 6)
> (nsq-div2 60)
(10 6)
> (time (nsq-div2 224403121196654400))
(time (nsq-div2 224403121196654400))
    5 collections
    94 ms elapsed cpu time, including 16 ms collecting
    104 ms elapsed real time, including 8 ms collecting
    21878568 bytes allocated, including 19696976 bytes reclaimed
(473753280 473670855)

We’ve gone from a minute to a tenth of a second. Most of the time is spent computing the 80640 divisors of 224403121196654400; factorization takes a blink of an eye, as all the factors are less than 40. Of course, it may be necessary for large values of n to use some faster method of computing the factors.

We used unique from the Standard Prelude. You can run the program at


Pages: 1 2

17 Responses to “Nearly-Square Divisors”

  1. Ernie said

    Another method is to start with the square root of n, rounded down, then decrement by one until a divisor is found. On my computer this took 0.6 sec.
    The pitfall with any method is to deal with a prime n.

  2. Paul said

    In Python. The divisors are scanned for the maximum value less equal isqrt(n).

    def nsd(n):
        s = isqrt(n)
        a = max(d for d in divisors(n) if d <= s)
        return a, n // a
  3. Matt W said

    @Ernie had the same idea! Here’s a solution that does that in Racket.

    (define (near-squares n)
      (let loop ((a (floor (sqrt n))))
        (let ((b (/ n a)))
          (if (and (integer? b)
                   (= n (* a b)))
              (list (inexact->exact a)
                    (inexact->exact b))
              (loop (sub1 a))))))
  4. Milbrae said

    I came up with the same idea as the previous commenters. For large n with a higher number of divisors this may become incredibly time consuming, e.g. n = 100#. So I guess there’s a quicker solution than simply testing all possible numbers from floor(sqrt(n)) downward.

  5. Milbrae said


    import math
    def nsd(n):
        s = (int)(math.sqrt(n))
        while n % s:
            s -= 1
        return s, n // s
    print (nsd(224403121196654400))

    Output in approx. 0.012s: (473670855, 473753280)

    Anyhow, this solution is based on the slow brute-force method. I’m almost certain there’s a much faster number-theoretical way to solve this for huge n.

  6. Paul said

    @Ernie and @Milbrae. The number N=224403121196654400 has an incredibly large number of divisors and is the worst-case scenario for a solution using divisors and the best-case scenario for the solution walking down from the root. Now try to use both methods in the range [N-10, N+10). Timing is 90 ms for the divisor solution and the other solution takes forever.

  7. Ernie said

    Paul: That is point I was trying to make in my first post: if N has very few divisors, decrementing from the sqrt may take forever, and if N is prime, well don’t ask.

  8. matthew said

    224403121196654400 is the 22nd “colossally abundant” number (and mentioned here:

    Finding nearly-square divisors seems about as hard as factoring (if we have a method for finding them we can apply it recursively to get a full factorization, and if we have a factorization, finding such divisors is straightforward).

    Fermat factorization seems relevant too, but maybe only applies to odd numbers.

  9. Milbrae said

    @Paul: You may have a point there. Anyhow, consider n having at least 30 distinct prime factors, each appearing once. n will then have 2**30 factors. You wouldn’t want to try almost all of them to find the correct NSD.
    There’s a similar problem on Project Euler ( I don’t think the people you have already solved this did it through simply factoring.

  10. matthew said

    @Milbrae: Good point, actually it’s a variant on the knapsack problem – find a maximal subset (or sub-multiset) of prime factors of n, the sum of whose logs is less than log n / 2 (and there are ways of solving the knapsack problem that are better than testing each alternative).

  11. Paul said

    @Milbrae. Thanks for pointing me to Euler 266. I solved for the product of first 30 primes with divisors and it took about 4 hours. The Euler problem needs the first 42 primes. That will indeed need another approach.

  12. Milbrae said

    @Matthew: A varint of knapsack? Could you elaborate on this?

  13. matthew said

    @Milbrae: One form of knapsack problem is: given a set of real numbers S, and a limit k, find the maximal subset sum less (or equal) to k (ie. find a subset with sum less than or equal to k, and greater or equal to the sum of any other such subset). This is exactly what we want for the nearly-square root of a product of single primes (as in the Project Euler problem) – S is the set of logs of the primes, and k is the log of the square root.

    Here’s a simple Haskell program that computes the log of the nearly square root of the product of the first 20 primes:

    -- k target s: return largest subset sum of s <= target
    k target [] = 0
    k target (a:s) =
      if a > target then k target s
      else max (a + k (target-a) s) (k target s)
    primes = [2,3,5,7,11,13,17,19,23,29,
    s = map log(reverse primes)
    target = (sum s)/2
    r = k target s
    main = print target >> print (k target s)

    Scan the tree of subsets, discarding a branch which cannot lead to a solution (here just subsets that would be too large – we could also keep track of the best solution found and discard branches that cannot lead to a better solution).

  14. Milbrae said

    @Matthew: Wow!! Works fine and extremely fast. I assume correctly the second line of the output is the exponent to e to get the result? I know practically nothing about Haskell.

  15. […] a recent exercise, we discussed the problem of computing the nearly square divisors of a composite number n = a · b, […]

  16. […] nearly square divisors exercise has generated a considerable amount of interest, and several excellent solutions in the comments. […]

  17. akshaya pandey said

    package test;

    import java.util.*;

    public class SquareDivisors {

    public static int squareDivisor(int n){
    int diff=10000;
    if (n < 0){
    return diff;
    List pairs = new ArrayList();
    //no need to look beyond sqrt hence check for (i*i )<=n
    for(int i=1;(i*i)<=n;i++){
    if (n%i==0){
    System.out.println("Pairs : "+i +" "+ (n/i));
    pairs.add(new Pairs(i,n/i));
    for(Pairs pair: pairs){
    diff= (diff < (Math.abs(pair.a-pair.b)))?diff:(Math.abs(pair.a-pair.b));
    return diff;

    public static void main(String args[]){
    System.out.println("Diff : "+squareDivisor(36));

    class Pairs{
    public Pairs(int a,int b){
    public int a,b;

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: