Truncatable primes: Difference between revisions
Content deleted Content added
m Put Sieve of Eratosthenes implementation in separate header file |
Added Prolog Solution |
||
Line 2,567: | Line 2,567: | ||
} |
} |
||
}</lang> |
}</lang> |
||
=={{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> |
|||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |