质因数分解程序

Question

这是我的第一个 Erlang 程序。我的代码需要帮助。我刚刚了解到我不能在 guards 中调用函数，所以我尝试在我的 factor/3 辅助函数中实现 "case"。代码编译，但出现以下错误：

***异常错误：计算算术表达式时出错在函数程序中：factor/3（program.erl，第 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])])).

Answer 1

我重写了你的代码，希望我能正确理解你的任务。

-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.

Answer 2

我修改了你的代码，因为你写的版本无法编译。

这里有很多问题。

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

变量不可变！你不能这样做，但你可以用新参数调用 first/2：

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

另外，这个函数如果以参数1调用是不会停止的，需要为此添加一个result。

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

此函数总是 return 0，因为它总是以检测到空列表结束。你应该写 isProduct([]) -> 1;

当你找到最后一个因素时，你将它插入到列表中，语法错误：使用 [First|Rest]; 而不是 [First, Rest];

当你要迭代时，第一个参数是当前剩余的Num，所以下一步应该是Num/Next with Next = first(Num)。注意语法中 [First|Rest] First 是一个元素（这里是一个整数），而 Rest 是一个列表，不能使用列表进行算术运算。

最后，你想在素数列表中添加一个新元素，它将是 Next = first(Num)，你必须将它放在列表的顶部并继续 Num div Next（这适用第一次调用 factor/3)

您的代码变为：

-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.

你的版本没有优化，因为你每次都先在 2 重新启动（当有很多素数时很重要）并且停止条件没有优化（当有一些 "big" 素数时很重要）。我会这样写：

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).

这是使用计时器测量的 2 个版本的结果：tc/3（在 windows 7 上），执行时间的差异很大，这个例子快了 15000 多倍：

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]}

质因数分解程序

Prime factorization program

erlang