CODEWITHSUNDEEP
erlang
user2355058
user2355058

Reputation:

Prime factorization program

This is my first Erlang program. I need help with my code. I just learned that I can not call functions in guards so I tried to impliment a "case" in my factor/3 helper function. The code compiles, but I get the following error:

*** exception error: an error occurred when evaluating an arithmetic expression in function program:factor/3 (program.erl, line 24) *

  -module(program).
  -export([first/1, isProduct/1, factor/1]).


  %returns the first prime factor of the parameter(an integer greater than    1) passed to the function
  first(Num) -> first(Num, 2). 

  %private helper function for first(Num)
  first(Num, Count) when (Num rem Count) == 0 -> Count;
  first(Num, Count) -> Count = Count + 1,
  first(Num, Count).


  %returns the prime factorization of Num as a list of prime numbers
  factor(Num) -> factor(Num, Num, 1, [Rest, first(Num)])

  %helper function for factor(Num)
  factor(Num, StaticNum, Count, [First|Rest]) when Count == StaticNum -> [First, Rest];  
  factor(Num, StaticNum, Count, [First|Rest]) ->
  factor(Num div lists:last([Rest]), StaticNum, (Count * [Rest]), [Rest|first(Num div lists:last([Rest])])).

Upvotes: 0

Views: 483

Answers (2)

Pascal
Pascal

Reputation: 14042

I modified your code because the version you wrote cannot compile.

There are many problems here.

first(Num, Count) ->
    Count = Count + 1,
    first(Num, Count).

Variable are not mutable! You cannot do this, but you can recall first/2 with new parameters:

first(Num, Count) ->
    first(Num, Count+1).

In addition, this function will never stop if it is called with the parameter 1. You need to add a result for this.

%returns the product of factors-in-a-list. 
isProduct([]) -> 0;
isProduct([First|Rest]) -> First * isProduct(Rest).

This function always return 0 since it always end with the detection of an empty list. You should write isProduct([]) -> 1;

When you find the last factor you insert it in the list with a bad syntax: use [First|Rest]; not [First, Rest];

when you want to iterate, the first parameter is the current remaining Num, so for the next step it should be Num/Next with Next = first(Num). Note that in the syntax [First|Rest] First is an element (here an integer), while Rest is a list, and you cannot use a list for arithmetic operation.

Last, you want to add a new element to the list of primes, it will be Next = first(Num) and you have to put it on top of the list and continue with Num div Next (this apply to the first call to factor/3)

your code becomes:

-module(program).
  -export([factor/1]).


  %returns the first prime factor of the parameter(an integer greater than    1) passed to the function
  first(1) -> 1;
  first(Num) -> first(Num, 2). 

  %private helper function for first(Num)
  first(Num, Count) when (Num rem Count) == 0 -> Count;
  first(Num, Count) -> first(Num, Count+1).

  %returns the product of factors-in-a-list. 
  isProduct([]) -> 1;
  isProduct([First|Rest]) -> First * isProduct(Rest).



  %returns the prime factorization of Num as a list of prime numbers
  factor(Num) when is_integer(Num), Num > 0 ->
    First = first(Num),
    factor(Num div First, Num,[First]).

  %helper function for factor(Num)
  factor(Num, StaticNum, [First|Rest]) ->
    case isProduct([First|Rest]) == StaticNum of 
      true -> [First|Rest];
      false -> 
          Next = first(Num),
          factor(Num div Next, StaticNum, [Next,First|Rest])
    end.

Your version is not optimized since you restart first at 2 every time (important when there are many prime factors) and the stop condition is not optimized (important when there are some "big" prime factors). I would write it this way:

decomp(N) when is_integer(N), (N > 0) -> 
    lists:reverse(decomp(N,[],2)).

decomp(N,R,I) when I*I > N -> [N|R];
decomp(N,R,I) when (N rem I) =:= 0 -> decomp(N div I,[I|R],I);
decomp(N,R,2) -> decomp(N,R,3);
decomp(N,R,I) -> decomp(N,R,I+2).

Here is the result for the 2 versions measured with timer:tc/3 (on windows 7), the difference of execution time is huge, more than 15000 time faster for this example:

2> timer:tc(program,factor,[1234567893200]).
{91349000,[3086419733,5,5,2,2,2,2]}
3> timer:tc(program,decomp,[1234567893200]).
{6000,[2,2,2,2,5,5,3086419733]}

Upvotes: 2

user4651282
user4651282

Reputation:

I rewrote you code,hope I rightly understand your task.

-module(program).
-export([first/1]).

first(Num) when Num >1,is_integer(Num) ->{ok,factor(Num,2)};
first(Num)-> {err,Num}.

factor(Num,Count) when Count>Num+1->[];
factor(Num,Count)->case Num rem Count of
                     0->[Count|factor(Num div Count,Count)];
                     _->factor(Num,Count+1)
                   end.

Upvotes: 1

Related Questions