/* 

  10001th prime (Rosetta code) in Picat.

  http://rosettacode.org/wiki/10001th_prime
  """
  Find and show on this page the 10001st prime number. 
  """

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

*/

main => go.

go ?=>
  println(nth_prime(10001)),

  % faster but probably cheating
  nth(10001,primes(200000),P),
  println(P),


  nl.
go => true.

% the 1_000_000'th prime is 15485863 (1min 37.61s)

% A Rust approach took 8h to find the 1_000_000_000'th prime::
% https://applied-math-coding.medium.com/computing-the-1-billions-prime-number-with-rust-e8c002baa4c
% How long does this Picat approach take?
go2 =>
  println(nth_prime(1_000_000_000)),
  nl.


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

nth_prime(Num, Choosen, Choosen, Num) :-
  prime(Num).
nth_prime(Num, Ix, Choosen, P) :-
  Ix < Choosen,
  % println(Num=Ix),
  next_prime(Num, P2),
  nth_prime(P2, Ix+1, Choosen, P).

next_prime(1,2).
next_prime(2,3).
next_prime(3,5).
next_prime(Num, P) :-
  next_prime2(Num+2, P).
next_prime2(Num, Num) :-
  prime(Num).
next_prime2(Num, P) :-
  next_prime2(Num+2,P).