Project Euler - Problem 7

Решение problem7 на projecteuler

Brute-force Python solution

#!/usr/bin/env python

import math

def is_prime(num):
    if num in [2, 3, 5, 7, 11, 13]:
        return True
    min_div = math.trunc(num ** .5)
    for divisor in xrange(min_div, num - 1):
        if num % divisor == 0:
            return False
    return True

def find_nth_prime(index_of_prime_to_find):
    cur_idx = 1
    num = 2
    while (cur_idx < index_of_prime_to_find):
        num += 1
        if is_prime(num):
            cur_idx += 1
    return num

def main():
    res = find_nth_prime(10001)
    print 'Answer: %s' % res

if __name__ == '__main__':
    main()

Время:

real 0m53.172s
user 0m53.096s
sys 0m0.049s

Brute-force Erlang solution

#!/usr/bin/env escript
-export([main/1]).

is_prime_ex(N, CurDivisor) when CurDivisor < N ->
    Rem = N rem CurDivisor,
    case Rem of
        0 -> false;
        _ -> is_prime_ex(N, CurDivisor + 1)
    end;
is_prime_ex(N, CurDivisor) when CurDivisor =:= N ->
    true.

is_prime(N) ->
    MinDivisor = erlang:round( math:sqrt(N) ),
    is_prime_ex(N, MinDivisor).

calc_nth_prime(IndexOfPrimeToFind, CurIndex, N) when CurIndex =:= IndexOfPrimeToFind ->
    N - 1;
calc_nth_prime(IndexOfPrimeToFind, CurIndex, N) when CurIndex < IndexOfPrimeToFind ->
    NewIndex = case is_prime(N) of
        true ->
            io:format("CurIndex=~p N=~p~n", [CurIndex+1, N]),
            CurIndex + 1;
        false ->
            CurIndex
    end,
    calc_nth_prime(IndexOfPrimeToFind, NewIndex, N + 1).

main(_) ->
    io:fwrite("Running problem007...~n"),
    IndexOfPrimeToFind = 10001,
    Res = calc_nth_prime(IndexOfPrimeToFind, 1, 2),
    io:format("Answer: ~w~n", [Res]),
    io:fwrite("Done.~n").

Время:

real 70m52.613s
user 70m18.016s
sys 0m4.075s

Concurrent brute-force Erlang solution

#!/usr/bin/env escript
-export([main/1]).

is_prime_ex(N, CurDivisor) when CurDivisor < N ->
    Rem = N rem CurDivisor,
    case Rem of
        0 -> false;
        _ -> is_prime_ex(N, CurDivisor + 1)
    end;
is_prime_ex(N, CurDivisor) when CurDivisor =:= N ->
    true.

is_prime(N) ->
    MinDivisor = erlang:round( math:sqrt(N) ),
    is_prime_ex(N, MinDivisor).

slave_proc(MasterPID) ->
    ChildPID = self(),
    receive
        {stop} -> ChildPID;
        {calc_is_prime, N} ->
            %io:format("[SLAVE]: {calc_is_prime, ~p}~n", [N]),
            Res = is_prime(N),
            MasterPID ! {is_prime_result, ChildPID, N, Res},
            %io:format("[SLAVE]: Result: {is_prime_result, ~p, ~p, ~p}~n", [ChildPID, N, Res]),
            slave_proc(MasterPID);
        Message ->
            io:format("[SLAVE]: Invalid message format: ~p~n", [Message])
    end.

create_pool(_MasterPID, Size) when Size =:= 0 ->
    [];
create_pool(MasterPID, Size) when Size > 0 ->
    SlavePID = spawn(fun() -> slave_proc(MasterPID) end),
    [SlavePID, create_pool(MasterPID, Size - 1)].

run_pool([], _N) ->
    true;
run_pool([SlavePID, Pool], N) ->
    SlavePID ! {calc_is_prime, N},
    run_pool(Pool, N + 1),
    true.

calc_prime(IndexOfPrimeToFind, CurPrimeIndex, N, _MaxCalculatedN) when CurPrimeIndex =:= IndexOfPrimeToFind ->
    N - 1;
calc_prime(IndexOfPrimeToFind, CurPrimeIndex, N, MaxCalculatedN) when CurPrimeIndex < IndexOfPrimeToFind ->
    receive
        {is_prime_result, ChildPID, N, true} ->
            io:format("[MASTER]: N=~p CurPrimeIndex=~p MaxCalculatedN=~p ~n", [N, CurPrimeIndex, MaxCalculatedN]),
            ChildPID ! {calc_is_prime, MaxCalculatedN + 1},
            calc_prime(IndexOfPrimeToFind, CurPrimeIndex + 1, N + 1, MaxCalculatedN + 1);
        {is_prime_result, ChildPID, N, false} ->
            ChildPID ! {calc_is_prime, MaxCalculatedN + 1},
            calc_prime(IndexOfPrimeToFind, CurPrimeIndex + 0, N + 1, MaxCalculatedN + 1)
    after
            1 ->
                calc_prime(IndexOfPrimeToFind, CurPrimeIndex, N, MaxCalculatedN)
    end.

main(_) ->
    io:fwrite("Running problem007...~n"),
    IndexOfPrimeToFind = 10001,
    PoolSize = 1000,

    MasterPID = self(),
    Pool = create_pool(MasterPID, PoolSize),
    run_pool(Pool, 2),
    Res = calc_prime(IndexOfPrimeToFind, 1, 2, PoolSize),

    io:format("Answer: ~w~n", [Res]),
    io:fwrite("Done.~n").

Время на 4-ядерном Core i7:

real 23m2.769s
user 173m25.874s
sys 2m14.798s

Время на 16-ядерном сервере:

real    15m14.150s
user    464m56.428s
sys     5m46.956s