algorithm - 了解素数生成器

Question

This site显示了生成素数列表的函数。

-module(eratosthenes).
-export([prime_numbers/1]).

% Sieve of Eratosthenes algorithm for finding all prime numbers up to N.
% http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

% Generate list of prime numbers up to N.
prime_numbers(N) when is_number(N) ->
prime_numbers(N, generate(N)).

prime_numbers(Max, [H|T]) when H * H =< Max ->
   [H | prime_numbers(Max, [R || R <- T, (R rem H) > 0])];

prime_numbers(_, T) -> T.

% Generate sequence 2..N
generate(N) -> generate(N, 2).

generate(Max, Max) -> [Max];

generate(Max, X) -> [X | generate(Max, X + 1)].

我不明白这个函数:

prime_numbers(_, T) -> T.

我用笔和纸做了这个例子:

prime_numbers(5)

1 - prime_numbers(5, [2,3,4,5])
2 - [2 | prime_numbers(5, [R || R <- [3,4,5], (R rem H) > 0)]
3 - [2 | prime_numbers(5, [3,5])]

prime_numbers(5, [3,5])

H * H =< MAX

3*3 =< 5 (False)

prime_numbers(_, T) -> T.

H = 3
T = 5

prime_numbers(5, [3,5]) = [5]

resp: [2,5]


or prime_numbers(5, [3,5]) = [3|[5]]

Answer 1

要理解这一点，您必须查看整个函数:

prime_numbers(Max, [H|T]) when H * H =< Max ->
   [H | prime_numbers(Max, [R || R <- T, (R rem H) > 0])];
prime_numbers(_, T) -> T.

我删除了一个换行符，因为它在这种情况下并不适用。 Erlang 中的习惯用法是像这样将函数的子句 放在一起。请注意，此函数有两个子句。我们对它们进行模式匹配^[0]。所以这就是:

“假设我们得到了一个名为 Max 的列表和一个至少包含一个 [H|T] 元素的列表。将列表解构为头元素 H 和列表的其余部分 T 。现在，这个模式有一个 when 守卫，所以它只适用于 H*H =< Max 。

如果这不匹配，说如果 when守卫是错误的，或者我们得到一个空列表 [] , 然后我们尝试匹配下一个子句 (_, T) .这个总是匹配并丢弃第一个参数 ( _ )。然后它匹配第二个参数中的任何内容并将其绑定(bind)到 T .然后它运行它的 body 。”

理解这一点的关键是理解模式匹配。一旦掌握了这些，代码就应该清晰易读。

^[0] 查看模式匹配的概念。它是许多语言的核心，例如 Prolog、ML、Haskell、Erlang、......