6

我正在通过 projecteuler.net 上的问题来学习如何在 Erlang 中编程，而我最难的是创建一个可以在不到一分钟的时间内创建所有低于 200 万的素数的素数生成器。使用顺序样式，我已经编写了三种类型的生成器，包括 Eratosthenes 的筛子，它们都没有表现得足够好。

我认为并发 Sieve 会很好用，但我收到 bad_arity 消息，我不知道为什么。关于我为什么遇到问题或如何正确编码的任何建议？

这是我的代码，注释掉的部分是我试图使事情并发的地方：

-模块（主服务器）。
-编译（export_all）。

开始（）->
    注册（素数，产卵（乐趣（）->循环（）结束））。

is_prime(N) -> rpc({is_prime,N})。

RPC（请求）->
    素数！{self(), 请求},
    收到
        {素数，响应} ->
            回复
    结尾。

循环（）->
    收到
        {来自，{is_prime，N}} ->
            如果
                N 从！{素数，假};
                N =:= 2 -> 从！{素数，真}；
                N rem 2 =:= 0 -> 从！{素数，假};
                真->
                    值 = is_not_prime(N),
                    Val = not(lists:member(true, Values)),
                    从 ！{素数，瓦尔}
            结尾，
            环形（）
    结尾。

for(N,N,_,F) -> [F(N)];
for(I,N,S,F) 当 I + S [F(I)|for(I+S, N, S, F)];
for(I,N,S,F) 当 I + S =:= N -> [F(I)|for(I+S, N, S, F)];
当 I + S > N -> [F(I)] 时，for(I,N,S,F)。

get_list(I, 限制) ->
    如果
        一世
            [我*A || 一种
            []
    结尾。

is_not_prime(N) ->
    对于(3, N, 2,
        乐趣（一）->
            列表 = get_list(I,trunc(N/I)),
            列表：成员（N，列表：展平（列表））
        结尾
        ）。

    %%L = for(1,N, fun() -> spawn(fun(I) -> wait(I,N) end) end),
    %%SeedList = [A || 一种  
    %% 列表：foreach(fun(X) ->
    %% 密码！{in_list, X}
    %% 结束，种子列表）
    %% 结束，L)。

%%等待(I,N) ->
%% 列表 = [I*A || 一个列表：成员（X，列表）
％％ 结尾。
4

10 回答 10

7

我使用 Go 和 channels 编写了一个 Eratosthenesque 并发初筛。

这是代码：http: //github.com/aht/gosieve

我在这里写了一篇博客：http: //blog.onideas.ws/eratosthenes.go

该程序可以在大约 10 秒内筛选出前一百万个素数（所有素数最多为 15,485,863）。筛子是并发的，但算法主要是同步的：goroutines（“actors”——如果你喜欢的话）之间需要太多的同步点，因此它们不能并行自由地漫游。

于 2010-03-06T07:40:50.307 回答
3

'badarity' 错误意味着你试图用错误数量的参数调用'fun'。在这种情况下...

%%L = for(1,N, fun() -> spawn(fun(I) -> wait(I,N) end) end),

for/3 函数期望 arity 1 的乐趣，而 spawn/1 函数期望 arity 0 的乐趣。试试这个：

L = for(1, N, fun(I) -> spawn(fun() -> wait(I, N) end) end),

传递给 spawn 的 fun 继承了其环境所需的部分（即 I），因此无需显式传递它。

虽然计算素数总是很有趣，但请记住，这不是 Erlang 旨在解决的问题。Erlang 是为大规模 actor 风格的并发而设计的。它很可能在所有数据并行计算的例子上表现相当糟糕。在许多情况下，例如 ML 中的顺序解决方案将非常快，以至于任何数量的内核都不足以让 Erlang 赶上，例如F# 和 .NET 任务并行库对于这些类型肯定是更好的工具的操作。

于 2008-09-22T08:54:14.920 回答
1

要考虑的另一种选择是使用概率素数生成。在乔的书（“主服务器”）中有一个使用米勒拉宾的例子，我认为......

于 2008-09-18T16:37:34.427 回答
1

您可以在此处找到四种不同的 Erlang 实现来查找素数（其中两种基于埃拉托色尼筛法）。此链接还包含比较 4 种解决方案性能的图表。

于 2009-01-26T14:35:50.040 回答
0

埃拉托色尼筛法相当容易实现，但是——正如您所发现的——不是最有效的。你试过阿特金筛子吗？

阿特金筛@维基百科

于 2008-09-18T04:32:26.027 回答
0

素数并行算法：http ://www.cs.cmu.edu/~scandal/cacm/node8.html

于 2008-09-18T07:45:41.010 回答
0

两个快速的单进程 erlang 素数生成器；sprimes 在 ~2.7 秒内生成 2m 以下的所有素数，fprimes 在我的计算机上生成 ~3 秒（具有 2.4 GHz Core 2 Duo 的 Macbook）。两者都基于 Eratosthenes 筛法，但由于 Erlang 最适用于列表而不是数组，因此两者都保留未消除的素数列表，检查当前头部的可分性并保留已验证素数的累加器。两者都还实现了一个主轮来对列表进行初始缩减。

-module(primes).
-export([sprimes/1, wheel/3, fprimes/1, filter/2]).    

sieve([H|T], M) when H=< M -> [H|sieve([X || X<- T, X rem H /= 0], M)];
sieve(L, _) -> L.
sprimes(N) -> [2,3,5,7|sieve(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), math:sqrt(N))].

wheel([X|Xs], _Js, M) when X > M ->
    lists:reverse(Xs);
wheel([X|Xs], [J|Js], M) ->
    wheel([X+J,X|Xs], lazy:next(Js), M);
wheel(S, Js, M) ->
    wheel([S], lazy:lazy(Js), M).

fprimes(N) ->
    fprimes(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), [7,5,3,2], N).
fprimes([H|T], A, Max) when H*H =< Max ->
    fprimes(filter(H, T), [H|A], Max);
fprimes(L, A, _Max) -> lists:append(lists:reverse(A), L).

filter(N, L) ->
    filter(N, N*N, L, []).
filter(N, N2, [X|Xs], A) when X < N2 ->
    filter(N, N2, Xs, [X|A]);
filter(N, _N2, L, A) ->
    filter(N, L, A).
filter(N, [X|Xs], A) when X rem N /= 0 ->
    filter(N, Xs, [X|A]);
filter(N, [_X|Xs], A) ->
    filter(N, Xs, A);
filter(_N, [], A) ->
    lists:reverse(A).

lazy:lazy/1 和lazy:next/1 指的是伪惰性无限列表的简单实现：

lazy(L) ->
    repeat(L).

repeat(L) -> L++[fun() -> L end].

next([F]) -> F()++[F];
next(L) -> L.

筛子生成素数并不是并发的好地方（但它可以使用并行性来检查可分性，尽管操作不够复杂，无法证明我迄今为止编写的所有并行过滤器的额外开销是合理的）。

`

于 2009-08-27T19:30:30.950 回答
-1

我喜欢欧拉计划。

关于素数发生器，我是埃拉托色尼筛法的忠实粉丝。

对于 2,000,000 以下的数字，您可以尝试一个简单的 isPrime 检查实现。我不知道你会如何在 erlang 中做到这一点，但逻辑很简单。

For Each NUMBER in LIST_OF_PRIMES
     If TEST_VALUE % NUMBER == 0
          Then FALSE
END
TRUE

if isPrime == TRUE add TEST_VALUE to your LIST_OF_PRIMES

iterate starting at 14 or so with a preset list of your beginning primes.

c# 在不到 1 分钟的时间内运行了一个这样的列表 2,000,000

编辑： 附带说明，Eratosthenes 的筛子可以轻松实现并快速运行，但是当您开始进入庞大的列表时会变得笨拙。最简单的实现，使用布尔数组和 int 值运行得非常快。问题是您开始遇到值大小以及数组长度的限制。-- 切换到字符串或位数组实现会有所帮助，但您仍然面临以较大值遍历列表的挑战。

于 2008-09-18T03:24:38.063 回答
-1

欧拉计划问题（我会说前 50 个问题中的大多数问题，如果不是更多的话）主要是关于蛮力的，在选择界限时需要一点独创性。

记住要测试任何 N 是否为素数（通过蛮力），您只需要查看它是否可被任何素数整除，直到 floor(sqrt(N)) + 1，而不是 N/2。

祝你好运

于 2008-09-18T03:24:39.670 回答
-1

这是vb版本

    'Sieve of Eratosthenes 
'http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 
'1. Create a contiguous list of numbers from two to some highest number n. 
'2. Strike out from the list all multiples of two (4, 6, 8 etc.). 
'3. The list's next number that has not been struck out is a prime number. 
'4. Strike out from the list all multiples of the number you identified in the previous step. 
'5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list). 
'6. All the remaining numbers in the list are prime. 
Private Function Sieve_of_Eratosthenes(ByVal MaxNum As Integer) As List(Of Integer)
    'tested to MaxNum = 10,000,000 - on 1.8Ghz Laptop it took 1.4 seconds
    Dim thePrimes As New List(Of Integer)
    Dim toNum As Integer = MaxNum, stpw As New Stopwatch
    If toNum > 1 Then 'the first prime is 2
        stpw.Start()
        thePrimes.Capacity = toNum 'size the list
        Dim idx As Integer
        Dim stopAT As Integer = CInt(Math.Sqrt(toNum) + 1)
        '1. Create a contiguous list of numbers from two to some highest number n.
        '2. Strike out from the list all multiples of 2, 3, 5. 
        For idx = 0 To toNum
            If idx > 5 Then
                If idx Mod 2 <> 0 _
                AndAlso idx Mod 3 <> 0 _
                AndAlso idx Mod 5 <> 0 Then thePrimes.Add(idx) Else thePrimes.Add(-1)
            Else
                thePrimes.Add(idx)
            End If
        Next
        'mark 0,1 and 4 as non-prime
        thePrimes(0) = -1
        thePrimes(1) = -1
        thePrimes(4) = -1
        Dim aPrime, startAT As Integer
        idx = 7 'starting at 7 check for primes and multiples 
        Do
            '3. The list's next number that has not been struck out is a prime number. 
            '4. Strike out from the list all multiples of the number you identified in the previous step. 
            '5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list). 
            If thePrimes(idx) <> -1 Then ' if equal to -1 the number is not a prime
                'not equal to -1 the number is a prime
                aPrime = thePrimes(idx)
                'get rid of multiples 
                startAT = aPrime * aPrime
                For mltpl As Integer = startAT To thePrimes.Count - 1 Step aPrime
                    If thePrimes(mltpl) <> -1 Then thePrimes(mltpl) = -1
                Next
            End If
            idx += 2 'increment index 
        Loop While idx < stopAT
        '6. All the remaining numbers in the list are prime. 
        thePrimes = thePrimes.FindAll(Function(i As Integer) i <> -1)
        stpw.Stop()
        Debug.WriteLine(stpw.ElapsedMilliseconds)
    End If
    Return thePrimes
End Function
于 2009-03-11T14:40:50.343 回答