Truncatable primes: Difference between revisions

=={{header|Prolog}}==

{{works with|SWI Prolog}}

<lang prolog>largest_left_truncatable_prime(N, N):-

is_left_truncatable_prime(N),

!.

largest_left_truncatable_prime(N, P):-

N > 1,

N1 is N - 1,

largest_left_truncatable_prime(N1, P).

is_left_truncatable_prime(P):-

is_prime(P),

is_left_truncatable_prime(P, P, 10).

is_left_truncatable_prime(P, _, N):-

P =< N,

!.

is_left_truncatable_prime(P, Q, N):-

Q1 is P mod N,

is_prime(Q1),

Q \= Q1,

N1 is N * 10,

is_left_truncatable_prime(P, Q1, N1).

largest_right_truncatable_prime(N, N):-

is_right_truncatable_prime(N),

!.

largest_right_truncatable_prime(N, P):-

N > 1,

N1 is N - 1,

largest_right_truncatable_prime(N1, P).

is_right_truncatable_prime(P):-

is_prime(P),

Q is P // 10,

(Q == 0, ! ; is_right_truncatable_prime(Q)).

main(N):-

find_prime_numbers(N),

largest_left_truncatable_prime(N, L),

writef('Largest left-truncatable prime less than %t: %t\n', [N, L]),

largest_right_truncatable_prime(N, R),

writef('Largest right-truncatable prime less than %t: %t\n', [N, R]).

main:-

main(1000000).</lang>

Module for finding prime numbers up to some limit:

<lang prolog>:- module(prime_numbers, [find_prime_numbers/1, is_prime/1]).

:- dynamic is_prime/1.

find_prime_numbers(N):-

retractall(is_prime(_)),

assertz(is_prime(2)),

init_sieve(N, 3),

sieve(N, 3).

init_sieve(N, P):-

P > N,

!.

init_sieve(N, P):-

assertz(is_prime(P)),

Q is P + 2,

init_sieve(N, Q).

sieve(N, P):-

P * P > N,

!.

sieve(N, P):-

is_prime(P),

!,

S is P * P,

cross_out(S, N, P),

Q is P + 2,

sieve(N, Q).

sieve(N, P):-

Q is P + 2,

sieve(N, Q).

cross_out(S, N, _):-

S > N,

!.

cross_out(S, N, P):-

retract(is_prime(S)),

!,

Q is S + P,

cross_out(Q, N, P).

cross_out(S, N, P):-

Q is S + P,

cross_out(Q, N, P).</lang>

{{out}}

<pre>

Largest left-truncatable prime less than 1000000: 998443

Largest right-truncatable prime less than 1000000: 739399

</pre>