Little Erlang Exercise 3

Problem Definition: Euler Problem 3

Obviously, these scripts did not actually implement the solution. The problem statement required to pick the largest factor, but I just realized I had not done it.

Python Solution

#
# The prime factors of 13195 are 5, 7, 13 and 29.
#
# What is the largest prime factor of the number 317584931803?
#

import sys

primes = []

def isprime(N):
  #  Original version use xrange, but caused
  #
  #  "OverflowException: long int too large to convert to int”
  # 
  #  when taking in a large number
  # 
  #  So, I have to use while loop to replace “for i in xrange(2, N):”
  #
  #  And in order to speed up the process, the prime calculation result
  #  is cached
  global primes

  # we have already tested it
  if N in primes:
    return True

  # use the prime results first 
  for i in primes:
    if (N % i) == 0:
      return False

  # now computation is required
  maxprime = 2
  if len(primes) > 0:
    maxprime = primes[-1]

  i = maxprime + 1
  while i < N:
    if (N % i) == 0:
      return False
    i = i + 1

  primes.append(N)
  return True


def factorise(N):
  #
  #  To factorise a integer
  #

  # short cut
  global primes
  res = []

  if N in primes:
    res.append(N)
    return res

  # original algorithm
  idx = 2
  while idx <= N:
    if isprime(idx):
      div, mod = divmod(N, idx)
      if mod == 0:
        res.append(idx)
        res.extend(factorise(div))
        break
    idx = idx + 1
  return res

if __name__ == ”__main__“:
  print factorise(int(sys.argv[1]))

Erlang Solution

Here comes the erlang version. There is some performance issue with this version. hopefully I would have some free time soon to improve the algorithm.

-module(p3).
-export([isprime/1, factorise/1]).

%%
%% prime means it is not divisible by any numbers other than 1 and itself.
%%
isprime(1) –>
 false;

isprime(2) –>
 true;

isprime(N) when N > 2 –>
 Pid = self(),
 C = lists:seq(2, N – 1),
 process_flag(trap_exit, true),
 lists:map(fun(Div) –>
               spawn_link(fun() –>
                   test_if_divisible(Pid, N, Div)
                   end)
               end, C),
 isprime_poll(length(C)).


%%
%% Message loop: to listen and receive message from voters
%%
isprime_poll(0) –>
 true;
isprime_poll(NumVote) –>
 receive
   {nondivisible, } –>
       isprime_poll(NumVote – 1);
   {divisible, } –>
       clean_mailbox(),
       false
 end.

%%
%% To clear away any messages in mailbox
%%
clean_mailbox() –>
 receive
   _ –>
     clean_mailbox()
   after 0 –> ok
 end.

%%
%%
%%
test_if_divisible(Pid, N, Div) –>
 case N rem Div of
   0 –> Pid ! {divisible, Div};
   _ –> Pid ! {nondivisible, Div}
 end.

%%%
%%% To factorise an integer – wrappers
%%%
factorise(N) when is_list(N) –>
   N1 = string:to_integer(N),
   factorise(N1, 2, []);

factorise(N) –>
   factorise(N, 2, []).

%%%
%%% To factorise an integer
%%%
factorise(N, Factor, Result) when Factor < N+1  –>
 case isprime(Factor) of
   true –>
     if
       (N rem Factor) == 0 –>
         %% io:format("Residual is 0 by Factor ~p~n”, [Factor]),
         factorise(N div Factor, 2, [Factor|Result]);
       true –>
         factorise(N, Factor + 1, Result)
     end;
   false –>
       factorise(N, Factor + 1, Result)
 end;

factorise(_, _, Result) –>
 R = lists:reverse(Result),
 %% io:format(“~p~n”, [R]),
 R.

Timeline

My development logbook

Little Erlang Exercise 3