Truncatable primes: Difference between revisions
m →{{header|REXX}}: un-dented a DO loop. -- ~~~~ |
m →{{header|REXX}}: combined two statements into one line. -- ~~~~ |
||
Line 1,405:
lp=0; rp=0
do j=n by -1 until lp\==0 & rp\==0; if pos(0,p.j)\==0 then iterate
do L=1 for 1 while lp==0
do k=1 for length(p.j)-1; _=right(p.j,k) /*truncate a #.*/
|
Revision as of 07:33, 12 September 2012
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
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.
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 | TRUE | 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 string to int = (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 trunc)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); trunc(s); IF UPB s = 0 THEN true exit FI; n := string to int(s) OD; FALSE EXIT true exit: TRUE FI
);
PROC get trunc prime = (INT in n, PROC(REF STRING)VOID trunc)VOID:(
FOR n FROM in n BY -1 TO 1 DO IF is trunc prime(n, trunc) 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 trunc prime(limit, (REF STRING s)VOID: s := s[LWB s+1:]); get 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 <stdlib.h>
- include <string.h>
- define MAX_PRIME 1000000
char *primes; int n_primes;
/* Sieve. If we were to handle 10^9 range, use bit field. Regardless,
* if a large amount of prime numbers need to be tested, sieve is fast. */
void init_primes() { int j; primes = malloc(sizeof(char) * MAX_PRIME); memset(primes, 1, MAX_PRIME); primes[0] = primes[1] = 0; int i = 2; while (i * i < MAX_PRIME) { for (j = i * 2; j < MAX_PRIME; j += i) primes[j] = 0; while (++i < MAX_PRIME && !primes[i]); } }
int left_trunc(int n) { int tens = 1; while (tens < n) tens *= 10;
while (n) { if (!primes[n]) return 0; tens /= 10; if (n < tens) return 0; n %= tens; } return 1; }
int right_trunc(int n) { while (n) { if (!primes[n]) return 0; n /= 10; } return 1; }
int main() { int n; int max_left = 0, max_right = 0; init_primes();
for (n = MAX_PRIME - 1; !max_left; n -= 2) if (left_trunc(n)) max_left = n;
for (n = MAX_PRIME - 1; !max_right; n -= 2) if (right_trunc(n)) max_right = n;
printf("Left: %d; right: %d\n", max_left, max_right); return 0; }</lang>output<lang>Left: 998443; right: 739399</lang>
Faster way of doing primality test for small numbers (1000000 isn't big), and generating truncatable primes bottom-up: <lang c>#include <stdio.h>
- define MAXN 1000000
int maxl, maxr;
int is_prime(int n) { int p; if (n % 3 == 0) return 0;
for (p = 6; p * p <= n; p += 6) if (!(n % (p + 1) && n % (p + 5))) return 0; return 1; }
void left(int n, int tens) { int i, nn;
if (n > maxl) maxl = n; if (n < MAXN / 10) for (tens *= 10, i = 1; i < 10; i++) if (is_prime(nn = i * tens + n)) left(nn, tens); }
void right(int n) { int i, nn; static int d[] = {1,3,7,9};
if (n > maxr) maxr = n; if (n < MAXN / 10) for (i = 1; i < 4; i++) if (is_prime(nn = n * 10 + d[i])) right(nn); }
int main(void) { left(3, 1); left(7, 1); right(3); right(5); right(7);
printf("%d %d\n", maxl, maxr);
return 0; }</lang>
- Output:
998443 739399
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>
CoffeeScript
<lang coffeescript># You could have symmetric algorithms for max right and left
- truncatable numbers, but they lend themselves to slightly
- different optimizations.
max_right_truncatable_number = (n, f) ->
# This algorithm only evaluates 37 numbers for primeness to # get the max right truncatable prime < 1000000. Its # optimization is that it prunes candidates for # the first n-1 digits before having to iterate through # the 10 possibilities for the last digit. if n < 10 candidate = n while candidate > 0 return candidate if f(candidate) candidate -= 1 else left = Math.floor n / 10 while left > 0 left = max_right_truncatable_number left, f right = 9 while right > 0 candidate = left * 10 + right return candidate if candidate <= n and f(candidate) right -= 1 left -= 1 throw Error "none found"
max_left_truncatable_number = (max, f) ->
# This is a pretty straightforward countdown. The first # optimization here would probably be to cache results of # calling f on small numbers. is_left_truncatable = (n) -> candidate = 0 power_of_ten = 1 while n > 0 r = n % 10 return false if r == 0 n = Math.floor n / 10 candidate = r * power_of_ten + candidate power_of_ten *= 10 return false unless f(candidate) true do -> n = max while n > 0 return n if is_left_truncatable n, f n -= 1 throw Error "none found"
is_prime = (n) ->
return false if n == 1 return true if n == 2 for d in [2..n] return false if n % d == 0 return true if d * d >= n
console.log "right", max_right_truncatable_number(999999, is_prime)
console.log "left", max_left_truncatable_number(999999, is_prime)
</lang>
output
<lang>
> coffee truncatable_prime.coffee
right 739399
left 998443
</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
Go
<lang go>package main
import "fmt"
func main() {
sieve(1e6) if !search(6, 1e6, "left", func(n, pot int) int { return n % pot }) { panic("997?") } if !search(6, 1e6, "right", func(n, _ int) int { return n / 10 }) { panic("7393?") }
}
var c []bool
func sieve(ss int) {
c = make([]bool, ss) c[1] = true for p := 2; ; { p2 := p * p if p2 >= ss { break } for i := p2; i < ss; i += p { c[i] = true } for { p++ if !c[p] { break } } }
}
func search(digits, pot int, s string, truncFunc func(n, pot int) int) bool {
n := pot - 1 pot /= 10
smaller:
for ; n >= pot; n -= 2 { for tn, tp := n, pot; tp > 0; tp /= 10 { if tn < tp || c[tn] { continue smaller } tn = truncFunc(tn, tp) } fmt.Println("max", s, "truncatable:", n) return true } if digits > 1 { return search(digits-1, pot, s, truncFunc) } return false
}</lang> Output:
max left truncatable: 998443 max right truncatable: 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>
Mathematica
<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]]]]]</lang>
Example usage:
n = PrimePi[1000000]; While[Not[LeftTruncatablePrimeQ[Prime[n]]], n--]; Prime[n] -> 998443 n = PrimePi[1000000]; While[Not[RightTruncatablePrimeQ[Prime[n]]], n--]; Prime[n] -> 739399
ooRexx
<lang ooRexx> -- find largest left- & right-truncatable primes < 1 million. -- an initial set of primes (not, at this time, we leave out 2 because -- we'll automatically skip the even numbers. No point in doing a needless -- test each time through primes = .array~of(3, 5, 7, 11)
-- check all of the odd numbers up to 1,000,000 loop j = 13 by 2 to 1000000
loop i = 1 to primes~size prime = primes[i] -- found an even prime divisor if j // prime == 0 then iterate j -- only check up to the square root if prime*prime > j then leave end -- we only get here if we don't find a divisor primes~append(j)
end
-- get a set of the primes that we can test more efficiently primeSet = .set~of(2) primeSet~putall(primes)
say 'The last prime is' primes[primes~last] "("primeSet~items 'primes under one million).'
say copies('-',66)
lastLeft = 0
-- we're going to use the array version to do these in order. We're still -- missing "2", but that's not going to be the largest loop prime over primes
-- values containing 0 can never work if prime~pos(0) \= 0 then iterate -- now start the truncations, checking against our set of -- known primes loop i = 1 for prime~length - 1 subprime = prime~right(i) -- not in our known set, this can't work if \primeset~hasIndex(subprime) then iterate prime end -- this, by definition, with be the largest left-trunc prime lastLeft = prime
end -- now look for right-trunc primes lastRight = 0 loop prime over primes
-- values containing 0 can never work if prime~pos(0) \= 0 then iterate -- now start the truncations, checking against our set of -- known primes loop i = 1 for prime~length - 1 subprime = prime~left(i) -- not in our known set, this can't work if \primeset~hasIndex(subprime) then iterate prime end -- this, by definition, with be the largest left-trunc prime lastRight = prime
end
say 'The largest left-truncatable prime is' lastLeft '(under one million).' say 'The largest right-truncatable prime is' lastRight '(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).
OpenEdge/Progress
<lang progress>FUNCTION isPrime RETURNS LOGICAL (
i_i AS INT
):
DEF VAR ii AS INT.
DO ii = 2 TO SQRT( i_i ):
IF i_i MODULO ii = 0 THEN RETURN FALSE.
END.
RETURN TRUE AND i_i > 1.
END FUNCTION. /* isPrime */
FUNCTION isLeftTruncatablePrime RETURNS LOGICAL (
i_i AS INT
):
DEF VAR ii AS INT. DEF VAR cc AS CHAR. DEF VAR lresult AS LOGICAL INITIAL TRUE. cc = STRING( i_i ).
DO WHILE cc > "": lresult = lresult AND isPrime( INTEGER( cc ) ). cc = SUBSTRING( cc, 2 ). END.
RETURN lresult.
END FUNCTION. /* isLeftTruncatablePrime */
FUNCTION isRightTruncatablePrime RETURNS LOGICAL (
i_i AS INT
):
DEF VAR ii AS INT. DEF VAR cc AS CHAR. DEF VAR lresult AS LOGICAL INITIAL TRUE. cc = STRING( i_i ).
DO WHILE cc > "": lresult = lresult AND isPrime( INTEGER( cc ) ). cc = SUBSTRING( cc, 1, LENGTH( cc ) - 1 ). END.
RETURN lresult.
END FUNCTION. /* isRightTruncatablePrime */
FUNCTION getHighestTruncatablePrimes RETURNS CHARACTER (
i_imax AS INTEGER
):
DEF VAR ii AS INT. DEF VAR ileft AS INT. DEF VAR iright AS INT.
DO ii = i_imax TO 1 BY -1 WHILE ileft = 0 OR iright = 0:
IF INDEX( STRING( ii ), "0" ) = 0 THEN DO: IF ileft = 0 AND isLeftTruncatablePrime( ii ) THEN ileft = ii. IF iright = 0 AND isRightTruncatablePrime( ii ) THEN iright = ii. END.
END.
RETURN SUBSTITUTE("Left: &1~nRight: &2", ileft, iright ).
END FUNCTION. /* getHighestTruncatablePrimes */
MESSAGE
getHighestTruncatablePrimes( 1000000 )
VIEW-AS ALERT-BOX.
</lang>
Output:
--------------------------- Message --------------------------- Left: 998443 Right: 739399 --------------------------- OK ---------------------------
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 parigp>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)
PL/I
<lang PL/I> tp: procedure options (main);
declare primes(1000000) bit (1); declare max_primes fixed binary (31); declare (i, k) fixed binary (31);
max_primes = hbound(primes, 1); call sieve;
/* Now search for primes that are right-truncatable. */ call right_truncatable;
/* Now search for primes that are left-truncatable. */ call left_truncatable;
right_truncatable: procedure;
declare direction bit (1); declare (i, k) fixed binary (31);
test_truncatable:
do i = max_primes to 2 by -1; if primes(i) then /* it's a prime */ do; k = i/10; do while (k > 0); if ^primes(k) then iterate test_truncatable; k = k/10; end; put skip list (i || ' is right-truncatable'); return; end; end;
end right_truncatable;
left_truncatable: procedure;
declare direction bit (1); declare (i, k, d, e) fixed binary (31);
test_truncatable:
do i = max_primes to 2 by -1; if primes(i) then /* it's a prime */ do; k = i; do d = 100000 repeat d/10 until (d = 10); e = k/d; k = k - e*d; if e = 0 then iterate test_truncatable; if ^primes(k) then iterate test_truncatable; end; put skip list (i || ' is left-truncatable'); return; end; end;
end left_truncatable;
sieve: procedure;
declare (i, j) fixed binary (31);
primes = '1'b; primes(1) = '0'b;
do i = 2 to sqrt(max_primes); do j = i+i to max_primes by i; primes(j) = '0'b; end; end;
end sieve;
end tp; </lang>
739399 is right-truncatable 998443 is left-truncatable
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>/*REXX pgm finds largest left- and right-truncatable primes < 1 million.*/ !.=0 /*placeholders for primes. */ p.1=2; p.2=3; p.3=5; p.4=7; p.5=11; p.6=13; p.7=17 /*some low primes.*/ !.2=1; !.3=1; !.4=1; !.7=1; !.11=1; !.13=1; !.17=1 /*low prime flags.*/ n=7 /*number of primes so far. */
do j=p.n+2 by 2 to 1000000 /*find all primes < 1,000,000. */ 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 while p.k**2<=j /*divide by known odd primes. */ if j//p.k==0 then iterate j /*divisible by X? Not prime. */ end /*k*/ n=n+1 /*bump number of primes found. */ p.n=j /*assign to sparse array. */ !.j=1 /*indicate that J is a prime. */ end /*j*/
say 'The last prime is' p.n " (there are "n 'primes under one million).' say copies('─',70) /*show a separator. */ lp=0; rp=0
do j=n by -1 until lp\==0 & rp\==0; if pos(0,p.j)\==0 then iterate do L=1 for 1 while lp==0 do k=1 for length(p.j)-1; _=right(p.j,k) /*truncate a #.*/ if \!._ then leave L /*Truncated # ¬ prime? Skip it. */ end /*k*/ lp=p.j end /*L*/
do R=1 for 1 while rp==0 do k=1 for length(p.j)-1; _=left(p.j,k) /*truncate a #.*/ if \!._ then leave R /*Truncated # ¬ prime? Skip it. */ end /*k*/ rp=p.j end /*R*/ end /*j*/
say 'The largest left-truncatable prime under one million is ' lp say 'The largest right-truncatable prime under one million is ' rp</lang> output
The last prime is 999983 (there are 78498 primes under one million). ────────────────────────────────────────────────────────────────────── The largest left-truncatable prime under one million is 998443 The largest right-truncatable prime under one million is 739399
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