Truncatable primes: Difference between revisions

=={{header|REXX}}==

<lang REXX>

/*find largest left- & right-truncatable primes < 1 million.*/

x.=0 /*placeholders for primes. */

p.=999 /*default value for P.n */

p.1= 2; x.2=1 /*1st prime: two. */

p.2= 3; x.3=1 /*2nd prime: three. */

p.3= 5; x.5=1 /*3rd prime: five. */

p.4= 7; x.7=1 /*4th prime: seven. */

p.5=11; x.11=1 /*5th prime: eleven. */

n=5 /*number of primes so far. */

do j=p.n+2 by 2 to 1000000 /*find all primes <1000000. */

if j//3 ==0 then iterate /*divisible by three? */

if right(j,1)==5 then iterate /*right-most digit a five? */

if j//7 ==0 then iterate /*divisible by seven? */

if j//11 ==0 then iterate /*divisible by eleven? */

/*the above 4 lines saves time*/

do k=6 /*divide by known odd primes. */

if p.k**2>j then leave /*only go up to sqrt(J). */

if j//p.k==0 then iterate j /*divisible by X? Not prime. */

end

n=n+1 /*bump number of primes found.*/

p.n=j /*assign to sparse array. */

x.j=1 /*indicate that J is a prime. */

end

say 'The last prime is' p.n "("n 'primes under one million).'

say copies('-',66) /*show a separator. */

lp=0

do j=1 for n /*find left-trunc. primes. */

y=p.j; g=y

if pos(0,y)\==0 then iterate /*if prime contains a 0, nope.*/

do k=1 for length(y)-1 /*test for prime, skip whole #*/

g=right(y,k); if \x.g then iterate j

end

lp=max(lp,y) /*choose the maximum so far. */

end

rp=0

do j=1 for n /*find left-trunc. primes. */

y=p.j; g=y

if pos(0,y)\==0 then iterate /*if prime contains a 0, nope.*/

do k=1 for length(y)-1 /*test for prime, skip whole #*/

g=left(y,k); if \x.g then iterate j

end

rp=max(rp,y) /*choose the maximum so far. */

end

say 'The largest left-truncatable prime is' lp '(under one million).'

say 'The largest right-truncatable prime is' rp '(under one million).'

</lang>

Output:

<pre style="height:30ex;overflow:scroll">

The last prime is 999983 (78498 primes under one million).

------------------------------------------------------------------

The largest left-truncatable prime is 998443 (under one million).

The largest right-truncatable prime is 739399 (under one million).

</pre>