A Divisor Apology

September 9, 2016

Today’s exercise is an apology from me, for writing an absolutely horrible piece of code.

While working on the nearly square divisors series of exercises, I discovered that the divisors function that I normally use is extremely slow when the number of divisors is large.

Your task is to write a function that returns the list of divisors of a number, and works with reasonable efficiency. 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.

Pages: 1 2

3 Responses to “A Divisor Apology”

  1. matthew said

    How does your program perform with, say, 278914005382139703576000?

  2. matthew said

    The answer is, not too bad (I was wondering about what would happen with lots of repeated factors resulting in the merge unique having to do more work):

    > (time (length (divisors4 278914005382139703576000)))
    cpu time: 471 real time: 472 gc time: 359
    1032192
    > (time (length (divisors4 40729680599249024150621323470)))
    cpu time: 1052 real time: 1054 gc time: 814
    2097152
    
  3. David said

    Erlang can calculate the divisors of those rather large numbers within 2 – 4 seconds. (matthew’s smaller number 1.6 seconds; 4 seconds for the bigger number.) I’m not claiming any credit, since the implementation is just a simple and rather naive list comprehension.

    % Divisors(n)
    % - Return a list of all of the divisors of n
    %
    divisors(N) when is_integer(N) -> divisors(factorize(N));
    
    divisors(L) when is_list(L) -> sort(divisors(L, [1])).
    
    divisors([], Divisors) -> Divisors;
    divisors([{P, R}|Factors], Divisors) ->
        divisors(Factors, [D * imath:pow(P, E) || D <- Divisors, E <- seq(0, R)]).
    

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: