読者です 読者をやめる 読者になる 読者になる

project euler problem 1-3 answer

prolog

練習がてら解いてみた。

回答

デフォルトのGnu PrologだとProblem3は速攻でヒープが足らなくなって落ちる。面倒なのでSWI-Prologを利用した。

problem1(N, Result) :- N1 is N - 1, problem1_sub(N1, Result, 0), !.
problem1_sub(0, Acc, Acc).
problem1_sub(N, Result, Acc) :-
        N > 0,
        N1 is N - 1,
        ((N mod 3 =:= 0 ; N mod 5 =:= 0) ->
        Acc1 is Acc + N;
        Acc1 is Acc),
        problem1_sub(N1, Result, Acc1).
problem1(1000,R).

problem2(N, Result) :- problem2_sub(N, Result, 1, 1, 0), !.
problem2_sub(N, Result, Fn1, Fn2, Acc) :-
        Fn is Fn1 + Fn2,
        N > Fn,
        (Fn mod 2 =:= 0 ->
         Acc1 is Acc + Fn ;
         Acc1 is Acc),
        problem2_sub(N, Result, Fn, Fn1, Acc1).
problem2_sub(_, Acc, _, _, Acc).

problem2(4000000,R).

not_divide_by(N, [Head | Rest]) :- N mod Head =\= 0, !, not_divide_by(N, Rest).
not_divide_by(_, []).
max_of([H|Rest], Max) :- max_of_sub(Rest, H, Max).
max_of_sub([], H, H).
max_of_sub([Head | Rest], CurrentMax, Max) :-
        Head > CurrentMax ->
        max_of_sub(Rest, Head, Max);
        max_of_sub(Rest, CurrentMax, Max).


problem3(N, Result) :- problem3_sub(N, Factors, [], [], 2),!, max_of(Factors, Result).
problem3_sub(1, Factors, Factors, _, _).
problem3_sub(N, Result, Factors, Primes, Current) :-
        Next is Current + 1,
        (not_divide_by(Current, Primes) ->
        (N mod Current =:= 0 -> problem3_sub_loop(N, Result, Factors, [Current | Primes], Current, Next);
                                problem3_sub(N, Result, Factors, [Current | Primes], Next));
        problem3_sub(N, Result, Factors, Primes, Next)).
problem3_sub_loop(N, Result, Factors, Primes, Current, Next) :-
        N mod Current =:= 0 ->
        N1 is N // Current, problem3_sub_loop(N1, Result, [Current| Factors], Primes, Current, Next) ;
        problem3_sub(N, Result, Factors, Primes, Next).

problem3(600851475143,R).