Truncatable primes: Difference between revisions
Content deleted Content added
(77 intermediate revisions by 26 users not shown) | |||
Line 1:
{{task|Prime Numbers}}
A truncatable prime is a prime number that when you successively remove digits from one end of the prime, you are left with a new prime number
;Examples:
The number '''997''' is called a ''left-truncatable prime'' as the numbers '''997''', '''97''', and '''7''' are all prime.
The number '''7393''' is a ''right-truncatable prime'' as the numbers '''7393''', '''739''', '''73''', and '''7''' formed by removing digits from its right are also prime.
No zeroes are allowed in truncatable primes.
Line 7 ⟶ 15:
;Related tasks:
* [[Find largest left truncatable prime in a given base]]
* [[Sieve of Eratosthenes]]
;See also:
* [http://mathworld.wolfram.com/TruncatablePrime.html Truncatable Prime] from MathWorld.]
<br><br>
=={{header|11l}}==
{{trans|C}}
<syntaxhighlight lang="11l">V MAX_PRIME = 1000000
V primes = [1B] * MAX_PRIME
primes[0] = primes[1] = 0B
V i = 2
L i * i < MAX_PRIME
L(j) (i * i .< MAX_PRIME).step(i)
primes[j] = 0B
i++
L i < MAX_PRIME & !primes[i]
i++
F left_trunc(=n)
V tens = 1
L tens < n
tens *= 10
L n != 0
I !:primes[n]
R 0B
tens I/= 10
I n < tens
R 0B
n %= tens
R 1B
F right_trunc(=n)
L n != 0
I !:primes[n]
R 0B
n I/= 10
R 1B
L(n) (MAX_PRIME - 1 .< 0).step(-2)
I left_trunc(n)
print(‘Left: ’n)
L.break
L(n) (MAX_PRIME - 1 .< 0).step(-2)
I right_trunc(n)
print(‘Right: ’n)
L.break</syntaxhighlight>
{{out}}
<pre>
Left: 998443
Right: 739399
</pre>
=={{header|Ada}}==
<syntaxhighlight lang="ada">
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Containers.Ordered_Sets;
Line 87 ⟶ 148:
end loop;
end Truncatable_Primes;
</syntaxhighlight>
Sample output:
<pre>
Line 99 ⟶ 160:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny].}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}
<
PROC is prime = (INT n)BOOL:(
Line 154 ⟶ 215:
write("Press Enter");
read(newline)
)</
Output:
<pre>
Line 162 ⟶ 223:
Press Enter
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">leftTruncatable?: function [n][
every? map 0..(size s)-1 'z -> to :integer slice s z (size s)-1
=> prime?
]
rightTruncatable?: function [n][
every? map 0..(size s)-1 'z -> to :integer slice s 0 z
=> prime?
]
upperLimit: 999999
loop range upperLimit .step:2 0 'x [
s: to :string x
if and? not? contains? s "0"
leftTruncatable? x [
print ["highest left-truncatable:" x]
break
]
]
loop range upperLimit .step:2 0 'x [
s: to :string x
if and? not? contains? s "0"
rightTruncatable? x [
print ["highest right-truncatable:" x]
break
]
]</syntaxhighlight>
{{out}}
<pre>highest left-truncatable: 998443
highest right-truncatable: 739399</pre>
=={{header|AutoHotkey}}==
<
MsgBox, % "Largest left-truncatable and right-truncatable primes less than one million:`n"
. "Left:`t" LTP(10 ** 6) "`nRight:`t" RTP(10 ** 6)
Line 219 ⟶ 317:
return, 1
}
}</
'''Output:'''
<pre>Largest left-truncatable and right-truncatable primes less than one million:
Left: 998443
Right: 739399</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f TRUNCATABLE_PRIMES.AWK
BEGIN {
limit = 1000000
for (i=1; i<=limit; i++) {
if (is_prime(i)) {
prime_count++
arr[i] = ""
if (truncate_left(i) == 1) {
max_left = max(max_left,i)
}
if (truncate_right(i) == 1) {
max_right = max(max_right,i)
}
}
}
printf("1-%d: %d primes\n",limit,prime_count)
printf("largest L truncatable: %d\n",max_left)
printf("largest R truncatable: %d\n",max_right)
exit(0)
}
function is_prime(x, i) {
if (x <= 1) {
return(0)
}
for (i=2; i<=int(sqrt(x)); i++) {
if (x % i == 0) {
return(0)
}
}
return(1)
}
function truncate_left(n) {
while (n != "") {
if (!(n in arr)) {
return(0)
}
n = substr(n,2)
}
return(1)
}
function truncate_right(n) {
while (n != "") {
if (!(n in arr)) {
return(0)
}
n = substr(n,1,length(n)-1)
}
return(1)
}
function max(x,y) { return((x > y) ? x : y) }
</syntaxhighlight>
{{out}}
<pre>
1-1000000: 78498 primes
largest L truncatable: 998443
largest R truncatable: 739399
</pre>
=={{header|Bracmat}}==
Primality test: In an attempt to compute the result of taking a (not too big, 2^32 or 2^64, depending on word size) number to a fractional power, Bracmat computes the prime factors of the number and checks whether the powers of prime factors make the fractional power go away. If the number is prime, the output of the computation is the same as the input.
<
& whl
' ( !i+-2:>0:?i
Line 243 ⟶ 401:
)
& out$("right:" !i)
)</
Output:
<pre>left: 998443
Line 249 ⟶ 407:
=={{header|C}}==
<
#include <stdlib.h>
#include <string.h>
Line 311 ⟶ 469:
printf("Left: %d; right: %d\n", max_left, max_right);
return 0;
}</
Faster way of doing primality test for small numbers (1000000 isn't big), and generating truncatable primes bottom-up:
<
#define MAXN 1000000
Line 360 ⟶ 518:
return 0;
}</
{{out}}
<pre>
Line 367 ⟶ 525:
=={{header|C sharp|C#}}==
<
using System.
class truncatable_primes
{
static void Main()
{
Console.Write("L " + L(m) + " R " + R(m) + " ");
var sw = System.Diagnostics.Stopwatch.StartNew();
}
{
for (uint d, d1 = 100; ; n -= 2)
while (d1 < n && d < (d = n % d1) && isP(d)) d1 *= 10;
if (d1 > n && isP(n)) return n; d1 = 100;
}
}
}
{
var p = new List<uint>() { 2, 3, 5, 7 }; uint n = 20, np;
for (int i = 1; i < p.Count; n = 10 * p[i++])
if (
if ((np = n + 7) >= m) break; if (isP(np)) p.Add(np);
if ((np = n + 9) >= m) break; if (isP(np)) p.Add(np);
}
return p[p.Count - 1];
}
{
if (n < 7) return n == 2 || n == 3 || n == 5;
if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0) return false;
n % (d + 06) == 0 || n % (d + 10) == 0 ||
n % (d + 22) == 0 || n % (d + 24) == 0) return false;
return true;
}</syntaxhighlight>
<pre>Output: L 998443 R 739399 24 μs</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <iostream>
#include "prime_sieve.hpp"
bool is_left_truncatable(const prime_sieve& sieve, int p) {
for (int n = 10, q = p; p > n; n *= 10) {
if (!sieve.is_prime(p % n) || q == p % n)
return false;
q = p % n;
}
return true;
}
bool is_right_truncatable(const prime_sieve& sieve, int p) {
for (int q = p/10; q > 0; q /= 10) {
if (!sieve.is_prime(q))
return false;
}
return true;
}
int main() {
const int limit = 1000000;
// find the prime numbers up to the limit
prime_sieve sieve(limit + 1);
int largest_left = 0;
int largest_right = 0;
// find largest left truncatable prime
for (int p = limit; p >= 2; --p) {
if (sieve.is_prime(p) && is_left_truncatable(sieve, p)) {
largest_left = p;
break;
}
}
// find largest right truncatable prime
for (int p = limit; p >= 2; --p) {
if (sieve.is_prime(p) && is_right_truncatable(sieve, p)) {
largest_right = p;
break;
}
}
// write results to standard output
std::cout << "Largest left truncatable prime is " << largest_left << '\n';
std::cout << "Largest right truncatable prime is " << largest_right << '\n';
return 0;
}</syntaxhighlight>
Contents of prime_sieve.hpp:
<syntaxhighlight lang="cpp">#ifndef PRIME_SIEVE_HPP
#define PRIME_SIEVE_HPP
#include <algorithm>
#include <vector>
/**
* A simple implementation of the Sieve of Eratosthenes.
* See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
*/
class prime_sieve {
public:
explicit prime_sieve(size_t);
bool is_prime(size_t) const;
private:
std::vector<bool> is_prime_;
};
/**
* Constructs a sieve with the given limit.
*
* @param limit the maximum integer that can be tested for primality
*/
inline prime_sieve::prime_sieve(size_t limit) {
limit = std::max(size_t(3), limit);
is_prime_.resize(limit/2, true);
for (size_t p = 3; p * p <= limit; p += 2) {
if (is_prime_[p/2 - 1]) {
size_t inc = 2 * p;
for (size_t q = p * p; q <= limit; q += inc)
is_prime_[q/2 - 1] = false;
}
}
}
/**
* Returns true if the given integer is a prime number. The integer
* must be less than or equal to the limit passed to the constructor.
*
* @param n an integer less than or equal to the limit passed to the
* constructor
* @return true if the integer is prime
*/
inline bool prime_sieve::is_prime(size_t n) const {
if (n == 2)
return true;
if (n < 2 || n % 2 == 0)
return false;
return is_prime_.at(n/2 - 1);
}
#endif</syntaxhighlight>
{{out}}
<pre>
Largest left truncatable prime is 998443
Largest right truncatable prime is 739399
</pre>
=={{header|Clojure}}==
<
(def prime?
Line 481 ⟶ 729:
((juxt ffirst (comp second second)) ,)
(map vector ["left truncatable: " "right truncatable: "] ,))
(["left truncatable: " 998443] ["right truncatable: " 739399])</
=={{header|CoffeeScript}}==
<
# truncatable numbers, but they lend themselves to slightly
# different optimizations.
Line 543 ⟶ 791:
console.log "right", max_right_truncatable_number(999999, is_prime)
console.log "left", max_left_truncatable_number(999999, is_prime)
</syntaxhighlight>
output
<syntaxhighlight lang="text">
> coffee truncatable_prime.coffee
right 739399
left 998443
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(defun start ()
(format t "Largest right-truncatable ~a~%" (max-right-truncatable))
Line 594 ⟶ 842:
((zerop (rem n d)) nil)
(t (primep-aux n (+ d 1)))))
</syntaxhighlight>
{{out}}
<pre>Largest right-truncatable 739399
Line 600 ⟶ 848:
=={{header|D}}==
<
std.range;
Line 633 ⟶ 881:
writeln("Largest right-truncatable prime in 2 .. ", n, ": ",
iota(n, 1, -1).filter!(isTruncatablePrime!false).front);
}</
{{out}}
<pre>Largest left-truncatable prime in 2 .. 1000000: 998443
Largest right-truncatable prime in 2 .. 1000000: 739399</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
procedure TruncatablePrimes(Memo: TMemo);
var Sieve: TPrimeSieve;
var I,P: integer;
function IsLeftTruncatable(P: integer): boolean;
{A prime is Left truncatable, if you can remove digits}
{one at a time from the left and it is still prime}
var S: string;
var P2: integer;
begin
Result:=False;
{Conver number to string}
S:=IntToStr(P);
{Delete one char from the left}
Delete(S,1,1);
while Length(S)>0 do
begin
{Zeros no allowed}
if S[1]='0' then exit;
{Convert back to number}
P2:=StrToInt(S);
{Exit if it is not prime}
if not Sieve.Flags[P2] then exit;
{Delete next char from left}
Delete(S,1,1);
end;
{If all truncated numbers are prime}
Result:=True;
end;
function IsRightTruncatable(P: integer): boolean;
{A prime is right truncatable, if you can remove digits}
{one at a time from the right and it is still prime}
var S: string;
var P2: integer;
begin
Result:=False;
{Conver number to string}
S:=IntToStr(P);
{Delete one char from the right}
Delete(S,Length(S),1);
while Length(S)>0 do
begin
{No zeros allowed}
if S[1]='0' then exit;
{Convert back to number}
P2:=StrToInt(S);
{exit if it is not prime}
if not Sieve.Flags[P2] then exit;
{Delete next char from the right}
Delete(S,Length(S),1);
end;
{If all truncated numbers are prime}
Result:=True;
end;
begin
Sieve:=TPrimeSieve.Create;
try
{Look at primes under 1 million}
Sieve.Intialize(1000000);
{Look for the highest Left Truncatable prime}
{Test all primes from 1 million down}
for I:=Sieve.PrimeCount-1 downto 0 do
begin
P:=Sieve.Primes[I];
{The first number that is Left Truncatable, will be the highest}
if IsLeftTruncatable(P) then
begin
Memo.Lines.Add(IntToStr(P));
break;
end;
end;
{Look for the highest Right Truncatable prime}
{Test all primes from 1 million down}
for I:=Sieve.PrimeCount-1 downto 0 do
begin
P:=Sieve.Primes[I];
if IsRightTruncatable(P) then
begin
Memo.Lines.Add(IntToStr(P));
break;
end;
end;
finally Sieve.Free; end;
end;
</syntaxhighlight>
{{out}}
<pre>
Largest Left Truncatable Prime: 998443
Largest Right Truncatable Prime: 739399
Elapsed Time: 14.666 ms.
</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang=text>
fastfunc isprim num .
if num < 2
return 0
.
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
func isright h .
while h > 0
if isprim h = 0
return 0
.
h = h div 10
.
return 1
.
func isleft h .
d = pow 10 (floor log10 h)
while h > 0
if isprim h = 0
return 0
.
if h div d = 0
return 0
.
h = h mod d
d /= 10
.
return 1
.
p = 999999
while isleft p = 0
p -= 2
.
print p
p = 999999
while isright p = 0
p -= 2
.
print p
</syntaxhighlight>
{{out}}
<pre>
998443
739399
</pre>
=={{header|EchoLisp}}==
<
;; does p include a 0 in its decimal representation ?
(define (nozero? n) (= -1 (string-index (number->string n) "0")))
Line 656 ⟶ 1,071:
(define (fact-trunc trunc)
(for ((p (in-range 999999 100000 -1))) #:break (when (trunc p) (writeln p) #t)))
</syntaxhighlight>
Output:
<
(fact-trunc left-trunc)
998443
(fact-trunc right-trunc)
739399
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 817 ⟶ 1,232:
end
</syntaxhighlight>
{{out}}
<pre>
Line 825 ⟶ 1,240:
=={{header|Elena}}==
ELENA 6.x :
<syntaxhighlight lang="elena">import extensions;
const MAXN = 1000000
extension mathOp
{
int n :=
if (n < 2)
if (n < 4)
if (n
if (n < 9)
if (n
int r := n
int f := 5
while (f <= r)
if ((n
f := f + 6
^ true
isRightTruncatable()
int n := self
while (n != 0)
ifnot (n
n := n / 10
^ true
isLeftTruncatable()
int n := self
int tens := 1
while (tens < n)
while (n != 0)
ifnot (n
tens := tens / 10
n := n - (n / tens * tens)
^ true
}
public program()
{
var n := MAXN
var max_lt := 0
var max_rt := 0
while
if(n
if ((max_lt == 0)
max_lt := n
if ((max_rt == 0)
max_rt := n
n := n - 1
console
console
console
}</syntaxhighlight>
{{out}}
<pre>
Line 928 ⟶ 1,343:
=={{header|Elixir}}==
{{trans|Ruby}}
<
defp left_truncatable?(n, prime) do
func = fn i when i<=9 -> 0
Line 974 ⟶ 1,389:
end
Prime.task</
{{out}}
Line 980 ⟶ 1,395:
Largest left-truncatable prime : 998443
Largest right-truncatable prime: 739399
</pre>
=={{header|Factor}}==
<syntaxhighlight lang="text">USING: formatting fry grouping.extras kernel literals math
math.parser math.primes sequences ;
IN: rosetta-code.truncatable-primes
CONSTANT: primes $[ 1,000,000 primes-upto reverse ]
: number>digits ( n -- B{} ) number>string string>digits ;
: no-zeros? ( seq -- ? ) [ zero? not ] all? ;
: all-prime? ( seq -- ? ) [ prime? ] all? ;
: truncate ( seq quot -- seq' ) call( seq -- seq' )
[ 10 digits>integer ] map ;
: truncate-right ( seq -- seq' ) [ head-clump ] truncate ;
: truncate-left ( seq -- seq' ) [ tail-clump ] truncate ;
: truncatable-prime? ( n quot -- ? ) [ number>digits ] dip
'[ @ all-prime? ] [ no-zeros? ] bi and ; inline
: right-truncatable-prime? ( n -- ? ) [ truncate-right ]
truncatable-prime? ;
: left-truncatable-prime? ( n -- ? ) [ truncate-left ]
truncatable-prime? ;
: find-truncatable-primes ( -- ltp rtp )
primes [ [ left-truncatable-prime? ] find nip ]
[ [ right-truncatable-prime? ] find nip ] bi ;
: main ( -- ) find-truncatable-primes
"Left: %d\nRight: %d\n" printf ;
MAIN: main</syntaxhighlight>
{{out}}
<pre>
Left: 998443
Right: 739399
</pre>
=={{header|Forth}}==
The prime sieve code is borrowed from [[Sieve of Eratosthenes#Forth]].
<syntaxhighlight lang="forth">: prime? ( n -- ? ) here + c@ 0= ;
: notprime! ( n -- ) here + 1 swap c! ;
: sieve ( n -- )
here over erase
0 notprime!
1 notprime!
2
begin
2dup dup * >
while
dup prime? if
2dup dup * do
i notprime!
dup +loop
then
1+
repeat
2drop ;
: left_truncatable_prime? ( n -- flag )
dup prime? invert if
drop false exit
then
dup >r
10
begin
2dup >
while
2dup mod
dup r> = if
2drop drop false exit
then
dup prime? invert if
2drop drop false exit
then
>r
10 *
repeat
2drop rdrop true ;
: right_truncatable_prime? ( n -- flag )
dup prime? invert if
drop false exit
then
begin
10 / dup 0 >
while
dup prime? invert if
drop false exit
then
repeat
drop true ;
: max_left_truncatable_prime ( n -- )
begin
dup 0 >
while
dup left_truncatable_prime? if . cr exit then
1-
repeat drop ;
: max_right_truncatable_prime ( n -- )
begin
dup 0 >
while
dup right_truncatable_prime? if . cr exit then
1-
repeat drop ;
1000000 constant limit
limit 1+ sieve
." Largest left truncatable prime: "
limit max_left_truncatable_prime
." Largest right truncatable prime: "
limit max_right_truncatable_prime
bye</syntaxhighlight>
{{out}}
<pre>
Largest left truncatable prime: 998443
Largest right truncatable prime: 739399
</pre>
=={{header|Fortran}}==
{{works with|Fortran|95 and later}}
<
implicit none
Line 1,071 ⟶ 1,619:
end if
end do
end program</
Output
<pre>Largest left truncatable prime below 1000000 is 998443
Line 1,078 ⟶ 1,626:
=={{header|FreeBASIC}}==
===Version 1===
<
Function isPrime(n As Integer) As Boolean
Line 1,133 ⟶ 1,681:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 1,142 ⟶ 1,690:
===Version 2===
Construct primes using previous found primes.
<
' compile with: fbc -s console
Line 1,224 ⟶ 1,772:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>
Line 1,231 ⟶ 1,779:
=={{header|Go}}==
<
import "fmt"
Line 1,285 ⟶ 1,833:
}
return false
}</
Output:
<pre>
Line 1,294 ⟶ 1,842:
=={{header|Haskell}}==
Using {{libheader|Primes}} from [http://hackage.haskell.org/packages/hackage.html HackageDB]
<
import Data.List
import Control.Arrow
Line 1,307 ⟶ 1,855:
let (ltp, rtp) = (head. filter leftT &&& head. filter rightT) primes1e6
putStrLn $ "Left truncatable " ++ show ltp
putStrLn $ "Right truncatable " ++ show rtp</
Output:
<
Left truncatable 998443
Right truncatable 739399</
Interpretation of the J contribution:
<
smallPrimes = filter isPrime digits
pow10 = iterate (*10) 1
Line 1,321 ⟶ 1,869:
lefT = liftM2 (.) (+) ((*) . mul10)
primesTruncatable f = iterate (concatMap (filter isPrime.flip map digits. f)) smallPrimes</
Output:
<
739399
*Main> maximum $ primesTruncatable lefT !! 5
998443</
==
<
N := 0 < integer(\arglist[1]) | 1000000 # primes to generator 1 to ... (1M or 1st arglist)
D := (0 < integer(\arglist[2]) | 10) / 2 # primes to display (10 or 2nd arglist)
Line 1,362 ⟶ 1,910:
procedure islefttrunc(P,x) #: return integer x if x and all left truncations of x are in P or fails
if *x = 0 | ( (x := integer(x)) & member(P,x) & islefttrunc(P,x[2:0]) ) then return x
end</
Sample output:<pre>There are 78498 prime numbers in the range 1 to 1000000
Line 1,369 ⟶ 1,917:
Largest right truncatable prime = 739399</pre>
==
Truncatable primes may be constructed by starting with a set of one digit prime numbers and then repeatedly adding a non-zero digit (combine all possibilities of a truncatable prime digit sequence with each digit) and, at each step, selecting the prime numbers which result.
Line 1,375 ⟶ 1,923:
In other words, given:
<
seed=: selPrime digits=: 1+i.9
step=: selPrime@,@:(,&.":/&>)@{@;</
Here, selPrime discards non-prime numbers from a list, so seed is the list 2 3 5 7.
Line 1,383 ⟶ 1,931:
The largest truncatable primes less than a million can be obtained by adding five digits to the prime seeds, then finding the largest value from the result.
<
998443
>./ step&digits^:5 seed NB. right truncatable
739399</
Note that we are using the same combining function and same basic procedure in both cases. The difference is which side of the number we add arbitrary digits to, for each step.
=={{header|Java}}==
<
public class Main {
Line 1,460 ⟶ 2,008:
}
}
</syntaxhighlight>
Output :
<pre>
Line 1,466 ⟶ 2,014:
Right Truncatable : 739399
</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
See [[Erd%C5%91s-primes#jq]] for a suitable implementation of `is_prime` as used here.
<syntaxhighlight lang="jq">def is_left_truncatable_prime:
def removeleft: recurse(if length <= 1 then empty else .[1:] end);
tostring
| index("0") == null and
all(removeleft|tonumber; is_prime);
def is_right_truncatable_prime:
def removeright: recurse(if length <= 1 then empty else .[:-1] end);
tostring
| index("0") == null and
all(removeright|tonumber; is_prime);
first( range(999999; 1; -2) | select(is_left_truncatable_prime)),
first( range(999999; 1; -2) | select(is_right_truncatable_prime))</syntaxhighlight>
{{out}}
<pre>
998443
739399
</pre>
=={{header|Julia}}==
There are several features of Julia that make solving this task easy. Julia has excellent built-in support for prime generation and testing. The built-in mathematical functions <tt>prevpow</tt> and <tt>divrem</tt> are quite handy for implementing <tt>isltruncprime</tt>.
<syntaxhighlight lang="julia">
function isltruncprime{T<:Integer}(n::T, base::T=10)
isprime(n) || return false
Line 1,506 ⟶ 2,081:
break
end
</syntaxhighlight>
{{out}}
Line 1,516 ⟶ 2,091:
=={{header|Kotlin}}==
{{trans|FreeBASIC}}
<
fun isPrime(n: Int) : Boolean {
Line 1,573 ⟶ 2,148:
println("Largest left truncatable prime : " + lMax.toString())
println("Largest right truncatable prime : " + rMax.toString())
}</
{{out}}
Line 1,582 ⟶ 2,157:
=={{header|Lua}}==
<
numbers = {}
Line 1,628 ⟶ 2,203:
print( "max_prime_left = ", max_prime_left )
print( "max_prime_right = ", max_prime_right )</
=={{header|
<syntaxhighlight lang="maple">
MaxTruncatablePrime := proc({left::truefalse:=FAIL, right::truefalse:=FAIL}, $)
local i, j, c, p, b, n, sdprimes, dir;
local tprimes := table();
if left = true and right = true then
error "invalid input";
elif right = true then
dir := "right";
else
dir := "left";
end if;
b := 10;
n := 6;
sdprimes := select(isprime, [seq(1..b-1)]);
for p in sdprimes do
if assigned(tprimes[p]) then
next;
end if;
i := ilog[b](p)+1;
j := 1;
while p < b^n do
if dir = "left" then
c := j*b^i + p;
else
c := p*b + j;
end if;
if j >= b or c > b^n then # we have tried all 1 digit extensions of p, add p to tprimes and move back 1 digit
tprimes[p] := p;
if i = 1 then # if we are at the first digit, go to the next 1 digit prime
break;
end if;
i := i - 1;
j := 1;
if dir = "left" then
p := p - iquo(p, b^i)*b^i;
else
p := iquo(p, b);
end if;
elif assigned(tprimes[c]) then
j := j + 1;
elif isprime(c) then
p := c;
i := i + 1;
j := 1;
else
j := j+1;
end if;
end do;
end do;
return max(indices(tprimes, 'nolist'));
end proc;</syntaxhighlight>
<pre>
> MaxTruncatablePrime(right); MaxTruncatablePrime(left);
739399
998443
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">LeftTruncatablePrimeQ[n_] := Times @@ IntegerDigits[n] > 0 &&
And @@ PrimeQ /@ ToExpression /@ StringJoin /@
Rest[Most[NestList[Rest, #, Length[#]] &[Characters[ToString[n]]]]]
RightTruncatablePrimeQ[n_] := Times @@ IntegerDigits[n] > 0 &&
And @@ PrimeQ /@ ToExpression /@ StringJoin /@
Rest[Most[NestList[Most, #, Length[#]] &[Characters[ToString[n]]]]]</
Example usage:
<pre>n = PrimePi[1000000]; While[Not[LeftTruncatablePrimeQ[Prime[n]]], n--]; Prime[n]
-> 998443
n = PrimePi[1000000]; While[Not[RightTruncatablePrimeQ[Prime[n]]], n--]; Prime[n]
-> 739399</pre>
Line 1,646 ⟶ 2,279:
=={{header|MATLAB}}==
largestTruncatablePrimes.m:
<
%Helper function for checking if a prime is left of right truncatable
Line 1,707 ⟶ 2,340:
end
end
</syntaxhighlight>
Solution for n = 1,000,000:
<syntaxhighlight lang="matlab">
>> largestTruncatablePrimes(1e6)
998443 is the largest left truncatable prime <= 1000000.
739399 is the largest right truncatable prime <= 1000000.
</syntaxhighlight>
=={{header|newLISP}}==
<syntaxhighlight lang="newlisp">
(define (prime? n) (= 1 (length (factor (int n)))))
(define (next-clean-prime n)
(do-until (and (prime? n) (not (find "0" (string n))))
(-- n)))
(define (check p i)
(let (s (string p))
(until (or (empty? s) (not (prime? s)))
(pop s i))
(when (empty? s)
;; Dynamic scope.
(if (zero? i) (setf lefty p) (setf righty p)))))
(define (foo , lefty righty)
(let (p 1000000)
(until (and lefty righty)
(set 'p (next-clean-prime p))
(unless lefty (check p 0))
(unless righty (check p -1)))
(list lefty righty)))
(foo)
</syntaxhighlight>
{{out}}
<pre>(998443 739399)</pre>
=={{header|Nim}}==
{{trans|Python}}
<syntaxhighlight lang="nim">import sets, strutils, algorithm
proc primes(n: int64): seq[int64] =
var multiples: HashSet[int64]
for i in 2..n:
if i notin multiples:
Line 1,728 ⟶ 2,389:
for j in countup(i*i, n, i.int):
multiples.incl j
proc truncatablePrime(n: int64): tuple[left
var
primelist: seq[string
for x in primes(n):
primelist.add($x)
reverse primelist
var primeset =
for n in primelist:
var alltruncs:
for i in 0..n.
alltruncs.incl n[
if alltruncs <= primeset:
result.left = parseInt(n)
break
for n in primelist:
var alltruncs:
for i in 0..n.
alltruncs.incl n[0..i]
if alltruncs <= primeset:
result.right = parseInt(n)
break
echo truncatablePrime(1000000i64)</syntaxhighlight>
{{out}}
<pre>(left: 998443, right: 739399)</pre>
=={{header|ooRexx}}==
<syntaxhighlight lang="oorexx">
-- find largest left- & right-truncatable primes < 1 million.
-- an initial set of primes (not, at this time, we leave out 2 because
Line 1,822 ⟶ 2,484:
say 'The largest right-truncatable prime is' lastRight '(under one million).'
</syntaxhighlight>
Output:
<pre>
Line 1,832 ⟶ 2,494:
=={{header|OpenEdge/Progress}}==
<
i_i AS INT
):
Line 1,913 ⟶ 2,575:
getHighestTruncatablePrimes( 1000000 )
VIEW-AS ALERT-BOX.
</
Output:
<pre>---------------------------
Line 1,926 ⟶ 2,588:
=={{header|PARI/GP}}==
This version builds the truncatable primes with up to k digits in a straightforward fashion. Run time is about 15 milliseconds, almost all of which is I/O.
<
my(v=[2,3,5,7],u,t=1,out=0);
for(i=1,n,
Line 1,955 ⟶ 2,617:
out
};
[left(6),right(6)]</
=={{header|Perl}}==
Typically with Perl we'll look for a CPAN module to make our life easier. This basically just follows the task rules:
{{libheader|ntheory}}
<
sub isltrunc {
my $n = shift;
Line 1,974 ⟶ 2,636:
for (reverse @{primes(1e6)}) {
if (isrtrunc($_)) { print "rtrunc: $_\n"; last; }
}</
{{out}}
<pre>ltrunc: 998443
rtrunc: 739399</pre>
We can be a little more Perlish and build up n-digit lists then select the last one:
<
my @lprimes = my @rprimes = (2,3,5,7);
Line 1,991 ⟶ 2,653:
for 2..6;
print "ltrunc: $lprimes[-1]\nrtrunc: $rprimes[-1]\n";</
Or we can do everything ourselves:
<
use warnings;
use strict;
Line 2,048 ⟶ 2,710:
}
print 'left ', join(', right ', @tprimes), "\n";</
{{out}}
<pre>left 998443, right 739399</pre>
=={{header|
A slightly different approach. Works up to N=8, quite fast - 10^8 in 5s with ~90% of time spent creating the basic sieve and ~10% propagation and final scan.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- standard sieve:</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">L</span><span style="color: #0000FF;">,</span><span style="color: #000000;">R</span> <span style="color: #000080;font-style:italic;">-- (with primes[i] as mini bit-field)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">L</span><span style="color: #0000FF;">+</span><span style="color: #000000;">R</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span><span style="color: #0000FF;">*</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">by</span> <span style="color: #000000;">i</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- propagate non-truncateables up the prime table:</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">N</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p10</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- ie 10, 100, .. 100_000</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">p10</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">p10</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- to 99, 999, .. 999_999</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p10</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">],</span><span style="color: #000000;">L</span><span style="color: #0000FF;">)+</span><span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">],</span><span style="color: #000000;">R</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pi</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pi</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxl</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxr</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pi</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">maxl</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">L</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">maxl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">maxr</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">R</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">maxr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">maxl</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">maxr</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?{</span><span style="color: #000000;">maxl</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxr</span><span style="color: #0000FF;">}</span>
<!--</syntaxhighlight>-->
{{Out}}
<pre>
{998443,739399}
</pre>
=={{header|PicoLisp}}==
<
(de truncatablePrime? (N Fun)
Line 2,080 ⟶ 2,774:
(until (truncatablePrime? (dec 'Left) cdr))
(until (truncatablePrime? (dec 'Right) '((L) (cdr (rot L)))))
(cons Left Right) )</
Output:
<pre>-> (998443 . 739399)</pre>
=={{header|Pike}}==
<syntaxhighlight lang="pike">bool is_trunc_prime(int p, string direction)
{
while(p) {
if( !p->probably_prime_p() )
return false;
if(direction == "l")
p = (int)p->digits()[1..];
else
p = (int)p->digits()[..<1];
}
return true;
}
void main()
{
bool ltp_found, rtp_found;
for(int prime = 10->pow(6); prime--; prime > 0) {
if( !ltp_found && is_trunc_prime(prime, "l") ) {
ltp_found = true;
write("Largest LTP: %d\n", prime);
}
if( !rtp_found && is_trunc_prime(prime, "r") ) {
rtp_found = true;
write("Largest RTP: %d\n", prime);
}
if(ltp_found && rtp_found)
break;
}
}</syntaxhighlight>
Output:
<pre>
Largest LTP: 999907
Largest RTP: 739399
</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
tp: procedure options (main);
declare primes(1000000) bit (1);
Line 2,153 ⟶ 2,883:
end tp;
</syntaxhighlight>
<pre>
739399 is right-truncatable
Line 2,160 ⟶ 2,890:
=={{header|PowerShell}}==
<
{
$isprime = @{}
Line 2,210 ⟶ 2,940:
"Largest Right Truncatable Prime: $lastrtprime"
}
}</
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<syntaxhighlight 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).</syntaxhighlight>
Module for finding prime numbers up to some limit:
<syntaxhighlight 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 + 2 * P,
cross_out(Q, N, P).
cross_out(S, N, P):-
Q is S + 2 * P,
cross_out(Q, N, P).</syntaxhighlight>
{{out}}
<pre>
Largest left-truncatable prime less than 1000000: 998443
Largest right-truncatable prime less than 1000000: 739399
</pre>
=={{header|PureBasic}}==
<
Procedure is_Prime(n)
Line 2,280 ⟶ 3,107:
y.s="Largest TruncateRight= "+Str(truncateright)
MessageRequester("Truncatable primes",x+#CRLF$+y)</
==
<
def primes(n):
Line 2,312 ⟶ 3,139:
return truncateleft, truncateright
print(truncatableprime(maxprime))</
'''Sample Output'''
<pre>(998443, 739399)</pre>
=={{header|Quackery}}==
<code>eratosthenes</code> and <code>sieve</code> are defined at [[Sieve of Eratosthenes#Quackery]].
<syntaxhighlight lang="quackery"> 1000000 eratosthenes
[ false swap
number$ witheach
[ char 0 =
if [ conclude not ] ] ] is haszero ( n --> b )
[ 10 / ] is truncright ( n --> n )
[ number$
behead drop $->n drop ] is truncleft ( n --> n )
[ dup isprime not iff
[ drop false ] done
dup haszero iff
[ drop false ] done
true swap
[ truncleft
dup 0 > while
dup isprime not iff
[ dip not ] done
again ] drop ] is ltruncatable ( n --> b )
[ dup isprime not iff
[ drop false ] done
dup haszero iff
[ drop false ] done
true swap
[ truncright
dup 0 > while
dup isprime not iff
[ dip not ] done
again ] drop ] is rtruncatable ( n --> b )
say "Left: "
1000000 times [ i ltruncatable if [ i echo conclude ] ]
cr
say "Right: "
1000000 times [ i rtruncatable if [ i echo conclude ] ]
cr</syntaxhighlight>
{{out}}
<pre>Left: 998443
Right: 739399
</pre>
=={{header|Racket}}==
<
#lang racket
(require math/number-theory)
Line 2,352 ⟶ 3,230:
998443
739399
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2015.09}}
<syntaxhighlight lang="raku" line>constant ltp = $[2, 3, 5, 7], -> @ltp {
$[ grep { .&is-prime }, ((1..9) X~ @ltp) ]
} ... *;
constant rtp = $[2, 3, 5, 7], -> @rtp {
$[ grep { .&is-prime }, (@rtp X~ (1..9)) ]
} ... *;
say "Highest ltp = ", ltp[5][*-1];
say "Highest rtp = ", rtp[5][*-1];</syntaxhighlight>
{{out}}
<pre>Highest ltp: 998443
Highest rtp: 739399</pre>
=={{header|REXX}}==
Extra code was added to the prime number generator as this is the section of the REXX program that consumes the vast majority of the computation time.
<syntaxhighlight lang
Parse Arg hi .
If hi=='' Then
Call genP /* generate primes up to hi */
/* find largest left truncatable Prime */
Do l=prime.0 By -1 /* search from top end; */
left.0=length(prime.l)
Do k=1 For length(prime.l)
_=right(prime.l,k)
left.k=_
If \is_prime._ Then
Iterate
End
Leave
End
/* find largest right truncated Prime */
Do r=prime.0 By -1 /* search from top end; */
right.0=length(prime.r)
Do k=1 For length(prime.r)
_=left(prime.r,k)
right.k=_
If \is_prime._ Then
Leave
End
Say 'The largest left-truncatable prime smaller than' hi 'is' prime.l
do i=left.0-1 to 1 By -1
say right(left.i,66)
End
Say 'The largest right-truncatable prime smaller than' hi 'is' prime.r
do i=right.0-1 to 1 By -1
say copies(' ',60)right.i
End
/*-----------------------------------------------------------------------------*/
genp:
Call time 'R'
Call init 2 3 5 7 11 13 17 19
Do j=21 to hi By 2
Select
When right(j,1)=5 Then Iterate
When j//3==0 Then Iterate
When j//7==0 Then Iterate
Otherwise Nop
End
Do k=5 While s.k<=j
If j//prime.k==0 Then
Iterate j
End
Call store j /* j is prime */
End
Say prime.0 'primes smaller than' hi '--' time('E') 'seconds'
Return
init:
Parse Arg plist
is_prime.=0
prime.=0
Do i=1 To words(plist)
Call store word(plist,i)
End
Return
store:
Parse Arg p
z=prime.0+1
prime.z=p
s.z=p*p
prime.0=z
is_prime.p=1
Return</syntaxhighlight>
{{out|output|text= when using the default inputs:}}
<pre>
78498 primes smaller than 1000000 -- 8.763000 seconds
The largest left-truncatable prime smaller than 1000000 is 998443
98443
8443
443
43
3
The largest right-truncatable prime smaller than 1000000 is 739399
73939
7393
739
73
7
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Truncatable primes
for n = 1000000 to 1 step -1
flag = 1
flag2 = 1
strn = string(n)
for nr = 1 to len(strn)
if strn[nr] = "0"
flag2 = 0
ok
next
if flag2 = 1
for m = 1 to len(strn)
strp = right(strn, m)
if isprime(number(strp))
else
flag = 0
exit
ok
next
if flag = 1
nend = n
exit
ok
ok
next
see "Largest left truncatable prime : " + nend + nl
for n = 1000000 to 1 step -1
flag = 1
strn = string(n)
for m = 1 to len(strn)
strp = left(strn, len(strn) - m + 1)
if isprime(number(strp))
else
flag = 0
exit
ok
next
if flag = 1
nend = n
exit
ok
next
see "Largest right truncatable prime : " + nend + nl
func isprime num
if (num <= 1) return 0 ok
if (num % 2 = 0 and num != 2) return 0 ok
for i = 3 to floor(num / 2) -1 step 2
if (num % i = 0) return 0 ok
next
return 1
</syntaxhighlight>
Output:
<pre>
Largest left truncatable prime : 998443
Largest right truncatable prime : 739399
</pre>
=={{header|RPL}}==
{{works with|HP|49}}
≪ → trunc
≪ <span style="color:red">1000000</span>
'''DO'''
'''DO''' PREVPRIME '''UNTIL''' DUP →STR <span style="color:red">"0"</span> POS NOT '''END'''
DUP <span style="color:red">1</span> SF
'''DO'''
trunc EVAL
'''IF''' DUP ISPRIME? NOT '''THEN''' <span style="color:red">1</span> CF '''END'''
'''UNTIL''' DUP <span style="color:red">9</span> ≤ <span style="color:red">1</span> FC? OR '''END'''
DROP
'''UNTIL''' <span style="color:red">1</span> FS? '''END'''
≫ ≫ '<span style="color:blue">XTRUNC</span>' STO
≪ →STR TAIL STR→ ≫ <span style="color:blue">XTRUNC</span>
≪ <span style="color:red">10</span> / IP ≫ <span style="color:blue">XTRUNC</span>
{{out}}
<pre>
2: 998443
1: 739399
</pre>
=={{header|Ruby}}==
<
truncatable?(n) {|i| i.to_s[1..-1].to_i}
end
Line 2,427 ⟶ 3,452:
p primes.detect {|p| left_truncatable? p}
p primes.detect {|p| right_truncatable? p}</
returns
Line 2,438 ⟶ 3,463:
The largest left truncatable prime less than 1000000 in base 10 is 998443
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn is_prime(n: u32) -> bool {
if n < 2 {
return false;
}
if n % 2 == 0 {
return n == 2;
}
if n % 3 == 0 {
return n == 3;
}
let mut p = 5;
while p * p <= n {
if n % p == 0 {
return false;
}
p += 2;
if n % p == 0 {
return false;
}
p += 4;
}
true
}
fn is_left_truncatable(p: u32) -> bool {
let mut n = 10;
let mut q = p;
while p > n {
if !is_prime(p % n) || q == p % n {
return false;
}
q = p % n;
n *= 10;
}
true
}
fn is_right_truncatable(p: u32) -> bool {
let mut q = p / 10;
while q > 0 {
if !is_prime(q) {
return false;
}
q /= 10;
}
true
}
fn main() {
let limit = 1000000;
let mut largest_left = 0;
let mut largest_right = 0;
let mut p = limit;
while p >= 2 {
if is_prime(p) && is_left_truncatable(p) {
largest_left = p;
break;
}
p -= 1;
}
println!("Largest left truncatable prime is {}", largest_left);
p = limit;
while p >= 2 {
if is_prime(p) && is_right_truncatable(p) {
largest_right = p;
break;
}
p -= 1;
}
println!("Largest right truncatable prime is {}", largest_right);
}</syntaxhighlight>
{{out}}
<pre>
Largest left truncatable prime is 998443
Largest right truncatable prime is 739399
</pre>
=={{header|Scala}}==
This example uses lazily evaluated lists. The functions to determine if a number is a truncatable prime construct a list of truncated numbers and check that all the elements in the list are prime.
<syntaxhighlight lang="scala">object TruncatablePrimes {
def main(args: Array[String]): Unit = {
val max = 1000000
println(
s"""|ltPrime: ${ltPrimes.takeWhile(_ <= max).last}
|rtPrime: ${rtPrimes.takeWhile(_ <= max).last}
|""".stripMargin)
}
def ltPrimes: LazyList[Int] = 2 #:: LazyList.from(3, 2).filter(isLeftTruncPrime)
def rtPrimes: LazyList[Int] = 2 #:: LazyList.from(3, 2).filter(isRightTruncPrime)
def isPrime(num: Int): Boolean = (num > 1) && !LazyList.range(3, math.sqrt(num).toInt + 1, 2).exists(num%_ == 0)
def isLeftTruncPrime(num: Int): Boolean = !num.toString.contains('0') && Iterator.unfold(num.toString){str => if(str.nonEmpty) Some((str.toInt, str.tail)) else None}.forall(isPrime)
def isRightTruncPrime(num: Int): Boolean = !num.toString.exists(_.asDigit%2 == 0) && Iterator.unfold(num.toString){str => if(str.nonEmpty) Some((str.toInt, str.init)) else None}.forall(isPrime)
}</syntaxhighlight>
{{out}}
<pre>ltPrime: 998443
rtPrime: 739399</pre>
=={{header|Sidef}}==
<
var p = %w(2 3 5 7);
var f = (
Line 2,453 ⟶ 3,581:
say t_prime(5, left: true)
say t_prime(5, left: false)</
{{out}}
<pre>
998443
739399
</pre>
=={{header|Swift}}==
{{trans|Rust}}
<syntaxhighlight lang="swift">func isPrime(_ n: Int) -> Bool {
if n < 2 {
return false
}
if n % 2 == 0 {
return n == 2
}
if n % 3 == 0 {
return n == 3
}
var p = 5
while p * p <= n {
if n % p == 0 {
return false
}
p += 2
if n % p == 0 {
return false
}
p += 4
}
return true
}
func isLeftTruncatable(_ p: Int) -> Bool {
var n = 10
var q = p
while p > n {
if !isPrime(p % n) || q == p % n {
return false
}
q = p % n
n *= 10
}
return true
}
func isRightTruncatable(_ p: Int) -> Bool {
var q = p / 10
while q > 0 {
if !isPrime(q) {
return false
}
q /= 10
}
return true
}
let limit = 1000000
var largestLeft = 0
var largestRight = 0
var p = limit
while p >= 2 {
if isPrime(p) && isLeftTruncatable(p) {
largestLeft = p
break
}
p -= 1
}
print("Largest left truncatable prime is \(largestLeft)")
p = limit
while p >= 2 {
if isPrime(p) && isRightTruncatable(p) {
largestRight = p
break
}
p -= 1
}
print("Largest right truncatable prime is \(largestRight)")</syntaxhighlight>
{{out}}
<pre>
Largest left truncatable prime is 998443
Largest right truncatable prime is 739399
</pre>
=={{header|Tcl}}==
<
# Optimized version of the Sieve-of-Eratosthenes task solution
Line 2,526 ⟶ 3,732:
break
}
}</
Output:
<pre>
Line 2,535 ⟶ 3,741:
searching for largest right-truncatable prime
FOUND:739399
</pre>
=={{header|Uiua}}==
{{Works with |Uiua|0.12.0-dev.1}}
<syntaxhighlight lang="uiua">
Mag ← 6
IsPrime ← =1⧻°/×
RAdd ← ♭⊞(+×10):1_3_7_9 # Add suffixes
LAdd ← ♭⊞+×⍜(ₙ10|⌈)⊢,+1⇡9 # Add prefixes
LastTP! ← ⊡¯1⍥(▽⊸≡IsPrime^!)-1Mag 2_3_5_7 # Build and filter
$"Right truncating: _"LastTP!RAdd
$"Left truncating: _"LastTP!LAdd
</syntaxhighlight>
{{out}}
<pre>
"Right truncating: 739399"
"Left truncating: 998443"
</pre>
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
start_time = Now
Line 2,607 ⟶ 3,830:
End If
End Function
</syntaxhighlight>
{{Out}}
Line 2,614 ⟶ 3,837:
Largest RTP from 1..1000000: 739399
Elapse Time(seconds) : 49
</pre>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
import "./math" for Int
var limit = 999999
var c = Int.primeSieve(limit, false)
var leftFound = false
var rightFound = false
System.print("Largest truncatable primes less than a million:")
var i = limit
while (i > 2) {
if (!c[i]) {
if (!rightFound) {
var p = (i/10).floor
while (p > 0) {
if (p%2 == 0 || c[p]) break
p = (p/10).floor
}
if (p == 0) {
System.print(" Right truncatable prime = %(Fmt.dc(0, i))")
rightFound = true
if (leftFound) return
}
}
if (!leftFound) {
var q = i.toString[1..-1]
if (!q.contains("0")) {
var p = Num.fromString(q)
while (q.count > 0) {
if (p%2 == 0 || c[p]) break
q = q[1..-1]
p = Num.fromString(q)
}
if (q == "") {
System.print(" Left truncatable prime = %(Fmt.dc(0, i))")
leftFound = true
if (rightFound) return
}
}
}
}
i = i - 2
}</syntaxhighlight>
{{out}}
<pre>
Largest truncatable primes less than a million:
Left truncatable prime = 998,443
Right truncatable prime = 739,399
</pre>
=={{header|XPL0}}==
<
func Prime(P); \Return true if P is a prime number
Line 2,658 ⟶ 3,934:
[IntOut(0, LeftTrunc); CrLf(0);
IntOut(0, RightTrunc); CrLf(0);
]</
Output:
Line 2,668 ⟶ 3,944:
=={{header|zkl}}==
Using [[Extensible prime generator#zkl]] and a one meg bucket of bytes, construct a yes/no lookup table for all primes <= one million (<80,000).
<
var pTable=Data(million+1,Int).fill(0); // actually bytes, all zero
Line 2,682 ⟶ 3,958:
while(ns){ if(not pTable[ns]) return(False); ns=ns[1,*]; }
True
}</
<
"%,d is a right truncatable prime".fmt(_).println();
[million..0,-1].filter1(leftTrunc):
"%,d is a left truncatable prime".fmt(_).println();</
{{out}}
<pre>
|