Параллельный главный генератор

Можно найти четыре различных реализации Erlang для нахождения простых чисел (два из которых основаны на Решете Эратосфена), здесь. Эта ссылка также содержит графики, сравнивающие производительность этих 4 решений.

Начала параллельны алгоритму: http://www.cs.cmu.edu/~scandal/cacm/node8.html

Другая альтернатива для рассмотрения должна использовать вероятностное главное поколение. Существует пример этого в книге Joe ("главный сервер"), который использует Miller-Rabin, я думаю...

Решето Эратосфена довольно легко реализовать, но - поскольку Вы обнаружили - не самое эффективное. Вы попробовали Решето Atkin?

Решето Atkin Википедия

Euler проблемы проекта (я сказал бы, что большинство первых 50, если не больше), главным образом о грубой силе со всплеском изобретательности в выборе Ваших границ.

Не забудьте тестировать любого, если N является главным (грубой силой), только необходимо видеть если его делимое любым началом до пола (sqrt (N)) + 1, не N/2.

Удачи

Я люблю Euler Проекта.

На предмет главных генераторов я - большой поклонник Решета Эратосфена.

В целях чисел под 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# выполнил список как это для 2,000,000 в хорошо под меткой 1 минуты

Править: На ноте стороны решето Эратосфена может быть реализовано легко и работает быстро, но становится громоздким, когда Вы начинаете входить в огромные списки. Самая простая реализация, с помощью булева массива и международных значений работает чрезвычайно быстро. Проблема состоит в том, что Вы начинаете сталкиваться с пределами для размера Вашего значения, а также длины Вашего массива. - Переключающийся на строку или bitarray реализацию помогает, но у Вас все еще есть проблема итерации через Ваш список в больших значениях.

вот 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

Два быстрых однопроцессных генератора простых чисел эрланга; sprimes генерирует все простые числа менее 2 м за ~ 2,7 секунды, fprimes ~ за 3 секунды на моем компьютере (Macbook с Core 2 Duo 2,4 ГГц). Оба основаны на Решете Эратосфена, но поскольку 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.

Генерация простых чисел ситами не является отличное место для параллелизма (но он может использовать параллелизм при проверке делимости, хотя операция недостаточно сложна, чтобы оправдать дополнительные накладные расходы всех параллельных фильтров, которые я написал до сих пор).

`

Я написал параллельное первичное решето в стиле Эратосфена, используя Go и каналы.

Вот код: http://github.com/aht/gosieve

Я писал об этом здесь: http://blog.onideas.ws/eratosthenes.go

Программа может отсеять первый миллион простых чисел (все простые числа до 15 485 863) примерно за 10 секунд. Сито является параллельным, но алгоритм в основном синхронный: между горутинами («актерами» - если хотите) требуется слишком много точек синхронизации, и поэтому они не могут свободно перемещаться параллельно.