project euler problem 1-3 answer
練習がてら解いてみた。
回答
デフォルトの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).