# Integer Factorization Using Backtracking with Erlang

By | December 18, 2016

In an earlier post I showed an algorithm to factorize integers using backtracking. The algorithm was implemented in python. Here we have now the same thing in erlang.

To run the code, copy the script and save it to a file named "factorize.erl".

Then enter a shell and compile the module using the following command:

```\$erlc factorize.erl
```

Now you can factorize an integer (in our example 129) with this command:

```\$escript factorize.beam 129
[3,43]
```

It seams, the erlang version is much faster than the python version.

Here is the Erlang code.

Have fun!

```

-module(factorize).

-export([
main/1
]).

getbit(X, N) ->
(X bsr N) band 1.

setbit(X, N, 1) ->
X bor (1 bsl N);
setbit(X, N, 0) ->
X band (bnot (1 bsl N)).

bitcmp(_I1, _I2, _N, _N)->
0;
bitcmp(I1, I2, N, I)->
B1=getbit(I1, I),
B2=getbit(I2, I),
if
B1 /= B2 ->
B1 - B2;
true ->
bitcmp(I1, I2, N, I + 1)
end.

bitcmp(I1, I2, N) ->
bitcmp(I1, I2, N, 0).

fac_check(I, 1, _I2, P, _Bits) when P == I ->
false;
fac_check(I, _I1, 1, P, _Bits) when P == I ->
false;
fac_check(I, _I1, _I2, P, _Bits) when P > I ->
false;
fac_check(I, _I1, _I2, P, _Bits) when P == I ->
true;
fac_check(I, _I1, _I2, P, Bits) ->
bitcmp(I, P, Bits).

fac_check(I, I1, I2, Bits) ->
fac_check(I, I1, I2, I1 * I2, Bits).

fac_run(I, _I1, _I2, _N, 4) ->
[I];
fac_run(I, I1, I2, N, B) ->
B1 = getbit(B, 0),
B2 = getbit(B, 1),
I1N = setbit(I1, N, B1),
I2N = setbit(I2, N, B2),

R = fac_check(I, I1N, I2N, N + 1),

case R of
true ->
lists:append(factorize(I1N), factorize(I2N));
0 ->
F=fac_run(I, I1N, I2N, N+1, 0),
if
F =/= [I] ->
F;
true ->
fac_run(I, I1, I2, N, B + 1)
end;
_ ->
fac_run(I, I1, I2, N, B + 1)
end.

fac_run(I, I1, I2) ->
fac_run(I, I1, I2, 0, 0).

factorize (I) ->
lists:sort(fac_run(I, 0, 0)).

main(Val) ->
[X]=Val,
R=factorize(list_to_integer(X)),
io:write(R),
io:format("~n").
```