/* 

  Euler #7 in Picat.

  Problem 7
  """
  By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see 
  that the 6^(th) prime is 13.

  What is the 10001^(st) prime number?
  """


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

*/

main => time(go).

go => euler7d.

% Neng-Fa's solution from http://picat-lang.org/euler/p7.pi
% slightly faster than euler7a
% 0.12s
euler7 => 
    I = 11,
    Count = 4,
    while (Count !== 10001)
        if (prime(I)) then    % prime defined in module math.
            Count := Count+1
	end,
	I := I + 2
    end,
    writef("The 10001st prime number is %w%n",I-2).
	


% slightly faster than euler7b
% 0.124s
euler7a =>
  P = 2,
  N = 1,
  while(N < 10001)      
     N := N+1,
     next_prime(P,P2),
     P := P2
  end,
  println(P).

% 0.125s
euler7b =>
   nth_prime(10001, P), 
   writeln(P).

next_prime(Num, P) => Num2 = Num + 1, next_prime2(Num2, P).
next_prime2(Num, P) ?=> prime(Num), P = Num.
next_prime2(Num, P) =>
   Num2 = Num+1,
   next_prime2(Num2,P).

nth_prime(Choosen, P) => 
   nth_prime(1,0,Choosen, P).

nth_prime(Num, Choosen, Choosen, P) ?=> prime(Num), P = Num.
nth_prime(Num, Ix, Choosen, P) =>
   Ix < Choosen,
   Ix2 = Ix + 1,
   next_prime(Num, P2),
   nth_prime(P2, Ix2, Choosen, P).


% This is faster, but it's cheating 
% since it's a too appropriate upper bound...
% 0.036s
euler7c =>
  P=primes(200000), 
  println(P[10001]).

% 
% Same idea as euler7c but little less cheating:
% Create a incrementally larger list of Primes 
% and see if we reached the 10001th prime.
%
% 0.04s
euler7d =>
  Found = false,
  foreach(I in 1..300, Found = false) 
    Primes=primes((2**I).to_integer()),
    if Primes.length >= 10001 then
      Found := Primes[10001]
    end
  end,
  println(Found).