[erlang-questions] learning Erlang: factoring primes
Mon May 7 03:44:05 CEST 2007
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.
More information about the erlang-questions