Truncatable primes
A truncatable prime is prime number that when you successively remove digits from one end of the prime, you are left with a new prime number; for example, 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.
You are encouraged to solve this task according to the task description, using any language you may know.
The task is to find the largest left-truncatable and right-truncatable primes less than one million.
C.f: Sieve of Eratosthenes; Truncatable Prime from Mathworld.
Ada
<lang Ada> with Ada.Text_IO; use Ada.Text_IO; with Ada.Containers.Ordered_Sets;
procedure Truncatable_Primes is
package Natural_Set is new Ada.Containers.Ordered_Sets (Natural); use Natural_Set;
Primes : Set; function Is_Prime (N : Natural) return Boolean is Position : Cursor := First (Primes); begin while Has_Element (Position) loop if N mod Element (Position) = 0 then return False; end if; Position := Next (Position); end loop; return True; end Is_Prime;
function Is_Left_Trucatable_Prime (N : Positive) return Boolean is M : Natural := 1; begin while Contains (Primes, N mod (M * 10)) and (N / M) mod 10 > 0 loop M := M * 10; if N <= M then return True; end if; end loop; return False; end Is_Left_Trucatable_Prime;
function Is_Right_Trucatable_Prime (N : Positive) return Boolean is M : Natural := N; begin while Contains (Primes, M) and M mod 10 > 0 loop M := M / 10; if M <= 1 then return True; end if; end loop; return False; end Is_Right_Trucatable_Prime;
Position : Cursor;
begin
for N in 2..1_000_000 loop if Is_Prime (N) then Insert (Primes, N); end if; end loop; Position := Last (Primes); while Has_Element (Position) loop if Is_Left_Trucatable_Prime (Element (Position)) then Put_Line ("Largest LTP from 1..1000000:" & Integer'Image (Element (Position))); exit; end if; Previous (Position); end loop; Position := Last (Primes); while Has_Element (Position) loop if Is_Right_Trucatable_Prime (Element (Position)) then Put_Line ("Largest RTP from 1..1000000:" & Integer'Image (Element (Position))); exit; end if; Previous (Position); end loop;
end Truncatable_Primes; </lang> Sample output:
Largest LTP from 1..1000000: 998443 Largest RTP from 1..1000000: 739399
ALGOL 68
Note: This specimen retains the original C coding style.
<lang algol68>#!/usr/local/bin/a68g --script #
PROC is prime = (INT n)BOOL:(
[]BOOL is short prime=(FALSE, TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE); IF n<=UPB is short prime THEN is short prime[n] # EXIT # ELSE IF NOT ODD n OR n MOD 3 = 0 THEN FALSE # EXIT # ELSE INT h:=ENTIER sqrt(n)+3; FOR a FROM 7 BY 6 WHILE a<h DO IF ( n MOD a = 0 | TRUE | n MOD (a-2) = 0 ) THEN false exit FI OD; TRUE # EXIT # FI FI EXIT false exit: FALSE
);
PROC atol = (STRING in a)INT:(
FILE f; STRING a:=in a; associate(f, a); INT i; get(f, i); close(f); i
);
PROC is trunc prime = (INT in n, PROC(REF STRING)VOID func)BOOL: (
INT n := in n; STRING s:=whole(n, 0); IF char in string("0", NIL, s) THEN FALSE # EXIT # ELSE WHILE is prime(n) DO s:=whole(n, 0); func(s); IF UPB s = 0 THEN true exit FI; n := atol(s) OD; FALSE EXIT true exit: TRUE FI
);
PROC get hi trunc prime = (INT in n, PROC(REF STRING)VOID func)VOID:(
FOR n FROM in n BY -1 TO 1 DO IF is trunc prime(n, func) THEN printf(($g(0)l$, n)); break FI OD; break: ~
);
main:(
INT limit = 1000000; printf(($g g(0) gl$,"Highest left- and right-truncatable primes under ",limit,":")); get hi trunc prime(limit, (REF STRING s)VOID: s:=s[LWB s+1:]); get hi trunc prime(limit, (REF STRING s)VOID: s:=s[:UPB s-1]); write("Press Enter"); read(newline)
)</lang> Output:
Highest left- and right-truncatable primes under 1000000: 998443 739399 Press Enter
C
<lang C>#include<stdio.h>
- include<string.h>
- include<stdlib.h>
- include<math.h>
int isprime(int n){
int isprm[]={0,0,1,1,0,1,0,1,0,0}; int a=7,h; if(n<10)return isprm[n]; if(!(n&1)||!(n%3))return 0; h=sqrt(n)+3; while(a<h){ if(!(n%a)||!(n%(a-2)))return 0; a+=6; } return 1;
}
void leftTrunc(char*s,int l){
memmove(s,s+1,l);
}
void rightTrunc(char*s,int l){
s[l-1]=0;
}
int isTruncPrime(int n,void(*func)(char*,int)){
char s[32]; while(isprime(n)){ ltoa(n,s,10); if(strchr(s,'0'))break; func(s,strlen(s)); if(!(n=atol(s)))return 1; } return 0;
}
void getHiTruncPrime(int n,void(*func)(char*,int)){
while(n--){ if(isTruncPrime(n,func)){ printf("%d\n",n); break; } }
}
int main(){
puts("Highest left- and right-truncatable primes under 1e6:"); getHiTruncPrime(1000000,leftTrunc); getHiTruncPrime(1000000,rightTrunc); puts("Press Enter"); getchar(); return 0;
}</lang> Output:
Highest left- and right-truncatable primes under 1e6: 998443 739399 Press Enter
C#
<lang csharp>using System; using System.Diagnostics;
namespace RosettaCode {
internal class Program { public static bool IsPrime(int n) { if (n<2) return false; if (n<4) return true; if (n%2==0) return false; if (n<9) return true; if (n%3==0) return false; var r = (int) Math.Sqrt(n); var f = 6-1; while (f<=r) { if (n%f==0 ||n%(f+2)==0) return false; f += 6; } return true; }
private static bool IsRightTruncatable(int n) { for (;;) { n /= 10; if (n==0) return true; if (!IsPrime(n)) return false; } }
private static bool IsLeftTruncatable(int n) { string c = n.ToString(); if (c.Contains("0")) return false; for (int i = 1; i<c.Length; i++) if (!IsPrime(Convert.ToInt32(c.Substring(i)))) return false; return true; }
private static void Main() { var sb = new Stopwatch(); sb.Start(); int lt = 0, rt = 0; for (int i = 1000000; i>0; --i) { if (IsPrime(i)) { if (rt==0 && IsRightTruncatable(i)) rt = i; else if (lt==0 && IsLeftTruncatable(i)) lt = i; if (lt!=0 && rt!=0) break; } } sb.Stop(); Console.WriteLine("Largest truncable left is={0} & right={1}, calculated in {2} msec.", lt, rt, sb.ElapsedMilliseconds); } }
}</lang>
Largest truncable left is=998443 & right=739399, calculated in 16 msec.
Clojure
<lang Clojure>(use '[clojure.contrib.lazy-seqs :only [primes]])
(def prime?
(let [mem (ref #{})
primes (ref primes)]
(fn [n] (dosync (if (< n (first @primes))
(@mem n) (let [[mems ss] (split-with #(<= % n) @primes)] (ref-set primes ss) ((commute mem into mems) n)))))))
(defn drop-lefts [n]
(let [dropl #(if (< % 10) 0 (Integer. (subs (str %) 1)))] (->> (iterate dropl n)
(take-while pos? ,) next)))
(defn drop-rights [n]
(->> (iterate #(quot % 10) n) next (take-while pos? ,)))
(defn truncatable-left? [n]
(every? prime? (drop-lefts n)))
(defn truncatable-right? [n]
(every? prime? (drop-rights n)))
user> (->> (for [p primes :while (< p 1000000) :when (not-any? #{\0} (str p)) :let [l? (if (truncatable-left? p) p 0) r? (if (truncatable-right? p) p 0)] :when (or l? r?)]
[l? r?]) ((juxt #(apply max-key first %) #(apply max-key second %)) ,) ((juxt ffirst (comp second second)) ,) (map vector ["left truncatable: " "right truncatable: "] ,))
(["left truncatable: " 998443] ["right truncatable: " 739399])</lang>
D
<lang d>import std.stdio, std.math, std.string, std.conv;
bool isPrime(int n) {
if (n <= 1) return false; foreach (i; 2 .. cast(int)sqrt(cast(real)n) + 1) if (!(n % i)) return false; return true;
}
bool isTruncatablePrime(bool left)(int n) {
string s = to!string(n); if (indexOf(s, '0') != -1) return false; foreach (i; 0 .. s.length) static if (left) { if (!isPrime(to!int(s[i .. $]))) return false; } else { if (!isPrime(to!int(s[0 .. i+1]))) return false; } return true;
}
void main() {
enum int n = 1_000_000; foreach_reverse (i; 2 .. n) if (isTruncatablePrime!true(i)) { writeln("Largest left-truncatable prime in 2 .. ", n, ": ", i); break; } foreach_reverse (i; 2 .. n) if (isTruncatablePrime!false(i)) { writeln("Largest right-truncatable prime in 2 .. ", n, ": ", i); break; }
}</lang> Output:
Largest left-truncatable prime in 2 .. 1000000: 998443 Largest right-truncatable prime in 2 .. 1000000: 739399
Fortran
<lang fortran>module primes_mod
implicit none logical, allocatable :: primes(:)
contains
subroutine Genprimes(parr)
logical, intent(in out) :: parr(:) integer :: i
! Prime sieve
parr = .true. parr (1) = .false. parr (4 : size(parr) : 2) = .false. do i = 3, int (sqrt (real (size(parr)))), 2 if (parr(i)) parr(i * i : size(parr) : i) = .false. end do
end subroutine
function is_rtp(candidate)
logical :: is_rtp integer, intent(in) :: candidate integer :: n
is_rtp = .true. n = candidate / 10 do while(n > 0) if(.not. primes(n)) then is_rtp = .false. return end if n = n / 10 end do
end function
function is_ltp(candidate)
logical :: is_ltp integer, intent(in) :: candidate integer :: i, n character(10) :: nstr
write(nstr, "(i10)") candidate is_ltp = .true. do i = len_trim(nstr)-1, 1, -1 n = mod(candidate, 10**i) if(.not. primes(n)) then is_ltp = .false. return end if end do
end function
end module primes_mod
program Truncatable_Primes
use primes_mod implicit none integer, parameter :: limit = 999999 integer :: i character(10) :: nstr
! Generate an array of prime flags up to limit of search
allocate(primes(limit)) call Genprimes(primes)
! Find left truncatable prime
do i = limit, 1, -1 write(nstr, "(i10)") i if(index(trim(nstr), "0") /= 0) cycle ! check for 0 in number if(is_ltp(i)) then write(*, "(a, i0)") "Largest left truncatable prime below 1000000 is ", i exit end if end do
! Find right truncatable prime
do i = limit, 1, -1 write(nstr, "(i10)") i if(index(trim(nstr), "0") /= 0) cycle ! check for 0 in number if(is_rtp(i)) then write(*, "(a, i0)") "Largest right truncatable prime below 1000000 is ", i exit end if end do
end program</lang> Output
Largest left truncatable prime below 1000000 is 998443 Largest right truncatable prime below 1000000 is 739399
Haskell
Using
from HackageDB
<lang haskell>import Data.Numbers.Primes(primes, isPrime) import Data.List import Control.Arrow
primes1e6 = reverse. filter (notElem '0'. show) $ takeWhile(<=1000000) primes
rightT, leftT :: Int -> Bool rightT = all isPrime. takeWhile(>0). drop 1. iterate (`div`10) leftT x = all isPrime. takeWhile(<x).map (x`mod`) $ iterate (*10) 10
main = do
let (ltp, rtp) = (head. filter leftT &&& head. filter rightT) primes1e6 putStrLn $ "Left truncatable " ++ show ltp putStrLn $ "Right truncatable " ++ show rtp</lang>
Output: <lang haskell>*Main> main Left truncatable 998443 Right truncatable 739399</lang>
Interpretation of the J contribution: <lang haskell>digits = [1..9] :: [Integer] smallPrimes = filter isPrime digits pow10 = iterate (*10) 1 mul10 = (pow10!!). length. show righT = (+) . (10 *) lefT = liftM2 (.) (+) ((*) . mul10)
primesTruncatable f = iterate (concatMap (filter isPrime.flip map digits. f)) smallPrimes</lang> Output: <lang haskell>*Main> maximum $ primesTruncatable righT !! 5 739399
- Main> maximum $ primesTruncatable lefT !! 5
998443</lang>
Icon and Unicon
<lang Icon>procedure main(arglist)
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) P := sieve(N) # from sieve task (modified) write("There are ",*P," prime numbers in the range 1 to ",N) if *P <= 2*D then every writes( "Primes: "|!sort(P)||" "|"\n" ) else every writes( "Primes: "|(L := sort(P))[1 to D]||" "|"... "|L[*L-D+1 to *L]||" "|"\n" ) largesttruncateable(P)
end
procedure largesttruncateable(P) #: find the largest left and right trucatable numbers in P local ltp,rtp
every x := sort(P)[*P to 1 by -1] do # largest to smallest if not find('0',x) then { /ltp := islefttrunc(P,x) /rtp := isrighttrunc(P,x) if \ltp & \rtp then break # until both found } write("Largest left truncatable prime = ", ltp) write("Largest right truncatable prime = ", rtp) return
end
procedure isrighttrunc(P,x) #: return integer x if x and all right truncations of x are in P or fails if x = 0 | (member(P,x) & isrighttrunc(P,x / 10)) then return x end
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</lang>
Sample output:
There are 78498 prime numbers in the range 1 to 1000000 Primes: 2 3 5 7 11 ... 999953 999959 999961 999979 999983 Largest left truncatable prime = 998443 Largest right truncatable prime = 739399
J
Truncatable primes may be constructed by starting with a set of one digit prime numbers and then repeatedly adding a non-zero digit (using the cartesian product of digit sequences) and, at each step, selecting the prime numbers which result.
In other words, given:
<lang j>selPrime=: #~ 1&p: seed=: selPrime digits=: 1+i.9 step=: selPrime@,@:(,&.":/&>)@{@;</lang>
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:
<lang j> >./ digits&step^:5 seed NB. left truncatable 998443
>./ step&digits^:5 seed NB. right truncatable
739399</lang>
Java
<lang Java> import java.util.BitSet;
public class Main {
public static void main(String[] args){
final int MAX = 1000000;
//Sieve of Eratosthenes (using BitSet only for odd numbers) BitSet primeList = new BitSet(MAX>>1); primeList.set(0,primeList.size(),true);
int sqroot = (int) Math.sqrt(MAX); primeList.clear(0); for(int num = 3; num <= sqroot; num+=2) { if( primeList.get(num >> 1) ) { int inc = num << 1; for(int factor = num * num; factor < MAX; factor += inc) { //if( ((factor) & 1) == 1) //{ primeList.clear(factor >> 1); //} } } } //Sieve ends...
//Find Largest Truncatable Prime. (so we start from 1000000 - 1 int rightTrunc = -1, leftTrunc = -1; for(int prime = (MAX - 1) | 1; prime >= 3; prime -= 2) { if(primeList.get(prime>>1)) { //Already found Right Truncatable Prime? if(rightTrunc == -1) { int right = prime; while(right > 0 && primeList.get(right >> 1)) right /= 10; if(right == 0) rightTrunc = prime; }
//Already found Left Truncatable Prime? if(leftTrunc == -1 ) { //Left Truncation String left = Integer.toString(prime); if(!left.contains("0")) { while( left.length() > 0 ){ int iLeft = Integer.parseInt(left); if(!primeList.get( iLeft >> 1)) break; left = left.substring(1); } if(left.length() == 0) leftTrunc = prime; } } if(leftTrunc != -1 && rightTrunc != -1) //Found both? then Stop loop { break; } } } System.out.println("Left Truncatable : " + leftTrunc); System.out.println("Right Truncatable : " + rightTrunc); } } </lang> Output :
Left Truncatable : 998443 Right Truncatable : 796339
Lua
<lang lua>max_number = 1000000
numbers = {} for i = 2, max_number do
numbers[i] = i;
end
for i = 2, max_number do
for j = i+1, max_number do if numbers[j] ~= 0 and j % i == 0 then numbers[j] = 0 end end
end
max_prime_left, max_prime_right = 2, 2 for i = 2, max_number do
if numbers[i] ~= 0 then local is_prime = true local l = math.floor( i / 10 ) while l > 1 do if numbers[l] == 0 then is_prime = false break end l = math.floor( l / 10 ) end if is_prime then max_prime_left = i end is_prime = true local n = 10; while math.floor( i % 10 ) ~= 0 and n < max_number do if numbers[ math.floor( i % 10 ) ] ~= 0 then is_prime = false break end n = n * 10 end if is_prime then max_prime_right = i end end
end
print( "max_prime_left = ", max_prime_left ) print( "max_prime_right = ", max_prime_right )</lang>
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. <lang>left(n)={ my(v=[2,3,5,7],u,t=1,out=0); for(i=1,n, t*=10; u=[]; for(j=1,#v, forstep(a=t,t*9,t, if(isprime(a+v[j]),u=concat(u,a+v[j])) ) ); out=v[#v]; v=vecsort(u) ); out }; right(n)={ my(v=[2,3,5,7],u,out=0); for(i=1,n, u=[]; for(j=1,#v, forstep(a=1,9,[2,4], if(isprime(10*v[j]+a),u=concat(u,10*v[j]+a)) ) ); out=v[#v]; v=u ); out }; [left(6),right(6)]</lang>
Perl 6
This uses a fairly naive isprime routine. It works but is slow.
<lang perl6> use v6; my %cache = <2 3 5 7 11 13 17 19 23> >>=>>> 1;
sub isprime ($test) {
return %cache{$test} if defined %cache{$test}; return (%cache{$test} = 0) if $test <= 25; my $r = floor($test ** .5); return (%cache{$test} = 0) unless $test % $_ for (2, 3, * + 2 ... * >= $r); return (%cache{$test} = 1);
}
sub trunc_prime ($type, $limit is copy) {
$limit += ($limit % 2 ?? 0 !! 1); for ($limit, * - 2 ... * < 2 ) -> $loop { next if $loop ~~ /0/; # No zeros allowed my $this = $loop; while $this.&isprime { $this.=subst($type, ); return $loop unless $this; } }
}
say "Largest Left Truncatable Prime < 1000000: ",trunc_prime(rx/^\d/, 1000000); say "Largest Right Truncatable Prime < 1000000: ",trunc_prime(rx/\d$/, 1000000); </lang> Output:
Largest Left Truncatable Prime < 1000000: 998443 Largest Right Truncatable Prime < 1000000: 739339
PicoLisp
<lang PicoLisp>(load "@lib/rsa.l") # Use the 'prime?' function from RSA package
(de truncatablePrime? (N Fun)
(for (L (chop N) L (Fun L)) (T (= "0" (car L))) (NIL (prime? (format L))) T ) )
(let (Left 1000000 Right 1000000)
(until (truncatablePrime? (dec 'Left) cdr)) (until (truncatablePrime? (dec 'Right) '((L) (cdr (rot L))))) (cons Left Right) )</lang>
Output:
-> (998443 . 739399)
PowerShell
<lang PowerShell>function IsPrime ( [int] $num ) {
$isprime = @{} 2..[math]::sqrt($num) | Where-Object { $isprime[$_] -eq $null } | ForEach-Object { $_ $isprime[$_] = $true for ( $i=$_*$_ ; $i -le $num; $i += $_ ) { $isprime[$i] = $false } } 2..$num | Where-Object { $isprime[$_] -eq $null }
}
function Truncatable ( [int] $num ) {
$declen = [math]::abs($num).ToString().Length $primes = @() $ltprimes = @{} $rtprimes = @{} 1..$declen | ForEach-Object { $ltprimes[$_]=@{}; $rtprimes[$_]=@{} } IsPrime $num | ForEach-Object { $lastltprime = 2 $lastrtprime = 2 } { $curprim = $_ $curdeclen = $curprim.ToString().Length $primes += $curprim if( $curdeclen -eq 1 ) { $ltprimes[1][$curprim] = $true $rtprimes[1][$curprim] = $true $lastltprime = $curprim $lastrtprime = $curprim } else { $curmod = $curprim % [math]::pow(10,$curdeclen - 1) $curdiv = [math]::floor($curprim / 10) if( $ltprimes[$curdeclen - 1][[int]$curmod] ) { $ltprimes[$curdeclen][$curprim] = $true $lastltprime = $curprim } if( $rtprimes[$curdeclen - 1][[int]$curdiv] ) { $rtprimes[$curdeclen][$curprim] = $true $lastrtprime = $curprim } } if( ( $ltprimes[$curdeclen - 2].Keys.count -gt 0 ) -and ( $ltprimes[$curdeclen - 1].Keys.count -gt 0 ) ) { $ltprimes[$curdeclen -2] = @{} } if( ( $rtprimes[$curdeclen - 2].Keys.count -gt 0 ) -and ( $rtprimes[$curdeclen - 1].Keys.count -gt 0 ) ) { $rtprimes[$curdeclen -2] = @{} } } { "Largest Left Truncatable Prime: $lastltprime" "Largest Right Truncatable Prime: $lastrtprime" }
}</lang>
PureBasic
<lang PureBasic>#MaxLim = 999999
Procedure is_Prime(n)
If n<=1 : ProcedureReturn #False ElseIf n<4 : ProcedureReturn #True ElseIf n%2=0: ProcedureReturn #False ElseIf n<9 : ProcedureReturn #True ElseIf n%3=0: ProcedureReturn #False Else Protected r=Round(Sqr(n),#PB_Round_Down) Protected f=5 While f<=r If n%f=0 Or n%(f+2)=0 ProcedureReturn #False EndIf f+6 Wend EndIf ProcedureReturn #True
EndProcedure
Procedure TruncateLeft(n)
Protected s.s=Str(n), l=Len(s)-1 If Not FindString(s,"0",1) While l>0 s=Right(s,l) If Not is_Prime(Val(s)) ProcedureReturn #False EndIf l-1 Wend ProcedureReturn #True EndIf
EndProcedure
Procedure TruncateRight(a)
Repeat a/10 If Not a Break ElseIf Not is_Prime(a) Or a%10=0 ProcedureReturn #False EndIf ForEver ProcedureReturn #True
EndProcedure
i=#MaxLim Repeat
If is_Prime(i) If Not truncateleft And TruncateLeft(i) truncateleft=i EndIf If Not truncateright And TruncateRight(i) truncateright=i EndIf EndIf If truncateleft And truncateright Break Else i-2 EndIf
Until i<=0
x.s="Largest TruncateLeft= "+Str(truncateleft) y.s="Largest TruncateRight= "+Str(truncateright)
MessageRequester("Truncatable primes",x+#CRLF$+y)</lang>
Python
<lang python>maxprime = 1000000
def primes(n):
multiples = set() prime = [] for i in range(2, n+1): if i not in multiples: prime.append(i) multiples.update(set(range(i*i, n+1, i))) return prime
def truncatableprime(n):
'Return a longest left and right truncatable primes below n' primelist = [str(x) for x in primes(n)[::-1]] primeset = set(primelist) for n in primelist: # n = 'abc'; [n[i:] for i in range(len(n))] -> ['abc', 'bc', 'c'] alltruncs = set(n[i:] for i in range(len(n))) if alltruncs.issubset(primeset): truncateleft = int(n) break for n in primelist: # n = 'abc'; [n[:i+1] for i in range(len(n))] -> ['a', 'ab', 'abc'] alltruncs = set([n[:i+1] for i in range(len(n))]) if alltruncs.issubset(primeset): truncateright = int(n) break return truncateleft, truncateright
print(truncatableprime(maxprime))</lang>
Sample Output
(998443, 739399)
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:
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).
Ruby
<lang ruby>def left_truncatable?(n)
return truncatable?(n, $left_truncate)
end
$left_truncate = proc do |n|
begin n = Integer(String(n)[1..-1]) rescue ArgumentError n = 0 end n
end
def right_truncatable?(n)
return truncatable?(n, $right_truncate)
end
$right_truncate = proc {|n| n/10}
def truncatable?(n, trunc_func)
return false if String(n).include? "0" loop do n = trunc_func.call(n) return true if n == 0 return false if not Prime.prime?(n) end
end
require 'prime' primes = Prime.each(1_000_000).to_a.reverse
p primes.detect {|p| left_truncatable? p} p primes.detect {|p| right_truncatable? p}</lang>
returns
998443 739399
Tcl
<lang tcl>package require Tcl 8.5
- Optimized version of the Sieve-of-Eratosthenes task solution
proc sieve n {
set primes [list] if {$n < 2} {return $primes} set nums [dict create] for {set i 2} {$i <= $n} {incr i} { dict set nums $i "" } set next 2 set limit [expr {sqrt($n)}] while {$next <= $limit} { for {set i $next} {$i <= $n} {incr i $next} {dict unset nums $i} lappend primes $next
dict for {next -} $nums break
} return [concat $primes [dict keys $nums]]
}
proc isLeftTruncatable n {
global isPrime while {[string length $n] > 0} {
if {![info exist isPrime($n)]} { return false } set n [string range $n 1 end]
} return true
} proc isRightTruncatable n {
global isPrime while {[string length $n] > 0} {
if {![info exist isPrime($n)]} { return false } set n [string range $n 0 end-1]
} return true
}
- Demo code
set limit 1000000 puts "calculating primes up to $limit" set primes [sieve $limit] puts "search space contains [llength $primes] members" foreach p $primes {
set isPrime($p) "yes"
} set primes [lreverse $primes]
puts "searching for largest left-truncatable prime" foreach p $primes {
if {[isLeftTruncatable $p]} {
puts FOUND:$p break
}
}
puts "searching for largest right-truncatable prime" foreach p $primes {
if {[isRightTruncatable $p]} {
puts FOUND:$p break
}
}</lang> Output:
calculating primes up to 1000000 search space contains 78498 members searching for largest left-truncatable prime FOUND:998443 searching for largest right-truncatable prime FOUND:739399