Menu

Subscribe

Project Euler Problem 3

on project euler, erlang, perl, python

Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Link to original description
Source code examples on Github

Erlang version 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p3
% vim:syn=erlang

-mode(compile).

main(_) ->
    io:format("Answer ~p ~n",[pr(1,600851475143,1)]).

pr(1, N, 1) when N rem 2 =:= 0                          -> pr(1, N, 2);
pr(1, N, A) when N rem 3 =:= 0, A < 3                   -> pr(1, N, A*3);
pr(_, N, A) when A > N                                  -> 0;
pr(K, N, A) when (N rem (6*K+1)) =:= 0, (6*K+1)*A =:= N -> 6*K+1;
pr(K, N, A) when (N rem (6*K-1)) =:= 0, (6*K-1)*A =:= N -> 6*K-1;   
pr(K, N, A)                                             ->
    case {N rem (6*K-1), N rem (6*K+1)} of
        {0, 0} -> pr(K+1, N, A*(6*K+1)*(6*K-1));
        {_, 0} -> pr(K+1, N, A*(6*K+1));
        {0, _} -> pr(K+1, N, A*(6*K-1));
        _      -> pr(K+1, N, A)
    end.

Erlang version 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p3_1
% vim:syn=erlang

-mode(compile).

main(_) ->
    Answer = i(2, 600851475143),
    io:format("Answer ~p ~n",[Answer]).

i(I, N) when I*I < N -> i(I+1, j(I, N));    
i(_, N) -> N.

j(I, N) when N rem I =:= 0 -> j(I, N div I);
j(_, N) -> N.

Perl version

1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/perl

use strict;

my ($i, $n) = (2, 600851475143);
while($i*$i < $n){
    $n /= $i while !($n % $i);
    $i++
}

print "Answer: $n \n";

Python version

1
2
3
4
5
6
7
8
9
10
#!/usr/bin/python

n = 600851475143
i = 2
while i * i < n:
    while n % i == 0: n = n / i
    i = i + 1

print "Answer: %d" % n