[erlang-questions] learning Erlang: factoring primes

[ok]

On 4 May 2007, at 7:20 pm, Martin Ankerl wrote:

> Hello everybody, I have just started learning Erlang and wrote one of
> my first programs. It is a very simple prime factoring program

which examines a whole lot of trial divisors that are not primes.
Not only that, after it has found a successful divisor M, on the
next iteration it will try 2..M-1 unsuccessfully all over again.

The second clause of next_factor/3 is useless; any calls that might
have matched it will match the first clause instead (because N rem N
is 0).  It is rather unpleasant the way the caller does the remainder
instead of next_factor/3 itself.

So let's try this:

factors(N) when integer(N), N >= 1 ->
     search(2, N, []).

search(M, N, L) when M*N > N ->
     lists:reverse(case N of 1 -> L ; _ -> [N|L] end);
search(M, N, L) when N rem M == 0 ->
     search(M, N div N, [M|L]);
search(M, N, L) ->
     search(M+1, N, L).

Note that I've replaced the "N = 1" termination test by an
"M*M > N" termination test.  For the reason, consider what
happens when N is a large prime number.

The main ideas behind these changes are entirely language-independent.