Adventures In Prolog - Euler7 and the Nth Prime

Building on our previous prime-related posts, today's post will cover a solution to Project Euler's 7th Problem, i.e. finding the 10001st prime. Now, the solution to this problem can be easily expressed in thought and then converted to some programming language …

Starting with the lowest and first prime – 2 - , we check each subsequent number j > i, for primality. Whenever we find a j such that j is prime, we increment a prime counter c by one and continue testing numbers k > j. This is done until c reaches the number 10001.

The Prolog code below is an expression of this idea, added with some prime numbers found during the process of finding the 10001st prime. This means, given the border of some prime interval, i.e. 100th prime = i and 200th prime = j, we may start looking for the 150th prime within the number interval [i,j], instead of starting at 2 and checking each number until the prime counter reaches 150. Also, we might have defined the euler_7 predicate to be dynamic, i.e. updatable, such that whenever we find some kth prime, it will be stored in the fact database.

%EULER7 the 10001 prime
euler_7(4409, 600) :- !.

euler_7(Out, Xth) :-
  Xth < 600, !,
  euler_7_t(2, 1, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 700, !,
  euler_7_t(4409, 600, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1000, !,
  euler_7_t(5279, 700, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1100, !,
  euler_7_t(7917, 1000, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1200, !,
  euler_7_t(8831, 1100, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 1500, !,
  euler_7_t(9733, 1200, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 2000, !,
  euler_7_t(12553, 1500, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 3000, !,
  euler_7_t(17389, 2000, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 4000, !,
  euler_7_t(27449, 3000, Xth, Out).
  
euler_7(Out, Xth) :-
  Xth < 5000, !,
  euler_7_t(37813, 4000, Xth, Out).

euler_7(Out, Xth) :-
  Xth < 7000,
  euler_7_t(48611, 5000, Xth, Out), !.

euler_7(Out, Xth) :-
  Xth < 10001,
  euler_7_t(70657, 7000, Xth, Out), !.

euler_7(Out, Xth) :-
  euler_7_t(104743, 10001, Xth, Out), !.


euler_7_t(P, Xth, Xth, P) :-
  is_prime(P), !.
  
euler_7_t(NP, Xth, Xth, P) :-
  NewPrime is NP + 1,
  euler_7_t(NewPrime, Xth, Xth, P), !.

euler_7_t(X, Xth, Gth, Prime) :-
  is_prime(X),
  Y is X + 1,
  Yth is Xth + 1,
  euler_7_t(Y, Yth, Gth, Prime), !.

euler_7_t(X, Xth, Gth, Prime) :-
  Y is X + 1,
  euler_7_t(Y, Xth, Gth, Prime).
%EULER7 the 10001 prime