/* 

  Euler #3 in Picat.

  Problem 3
  """
  The prime factors of 13195 are 5, 7, 13 and 29.
  What is the largest prime factor of the number 600851475143 ?
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.
main => go.

go => time(euler3).

% 0.0s
euler3 => 
   600851475143.factors().max().println(),
   600851475143.factors().println(),
   nl.

% slower: 0.54s
euler3b =>
   prime_decomp(600851475143, P), 
   Max = max(P),
   writeln(Max).

% 0.2s
euler3c =>
   V=600851475143,
   writeln(max([P : P in V.sqrt().floor().primes(), V mod P == 0])).


prime_decomp(N, P) =>
     P = [J: J in 1..1+ceiling(sqrt(N)), N mod J == 0, prime_cached(J)].


alldivisorsM(N,Div) = [Divisors,NewN] =>
   M = N,
   Divisors1 = [],
   while (M mod Div == 0) 
      Divisors1 := Divisors1 ++ [Div],
      M := M div Div
   end,
   NewN := M,
   Divisors = Divisors1.

factors(N) = Factors =>
     M = N,
     Factors1 = [],
     while (M mod 2 == 0) 
         Factors1 := Factors1 ++ [2],  
         M := M div 2 
     end,
     T = 3,
     
     while (M > 1, T < 1+(sqrt(M)))
        if M mod T == 0 then
           [Divisors, NewM] = alldivisorsM(M, T),
           Factors1 := Factors1 ++ Divisors,
           M := NewM
        end,
        T := T + 2
     end,
     if M > 1 then Factors1 := Factors1 ++ [M] end,
     Factors = Factors1.

table
prime_cached(N) => prime(N).