## 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)]).
```