Substring primes

From Rosetta Code
Substring primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task

Find all primes in which all substrings (in base ten) are also primes.

This can be achieved by filtering all primes below 500 (there are 95 of them), but there are better ways.

Advanced

Solve by testing at most 15 numbers for primality. Show a list of all numbers tested that were not prime.

11l

Translation of: Go
F is_prime(n)
   I n == 2
      R 1B
   I n < 2 | n % 2 == 0
      R 0B
   L(i) (3 .. Int(sqrt(n))).step(2)
      I n % i == 0
         R 0B
   R 1B

V results = [2, 3, 5, 7]
V odigits = [3, 7]
[Int] discarded
V tests = 4

V i = 0
L i < results.len
   V r = results[i]
   i++
   L(od) odigits
      I (r % 10) != od
         V n = r * 10 + od
         I is_prime(n)
            results.append(n)
         E
            discarded.append(n)
         tests++

print(‘There are ’results.len‘ primes where all substrings are also primes, namely:’)
print(results)
print("\nThe following numbers were also tested for primality but found to be composite:")
print(discarded)
print("\nTotal number of primality tests = "tests)
Output:
There are 9 primes where all substrings are also primes, namely:
[2, 3, 5, 7, 23, 37, 53, 73, 373]

The following numbers were also tested for primality but found to be composite:
[27, 57, 237, 537, 737, 3737]

Total number of primality tests = 15

Action!

INCLUDE "H6:SIEVE.ACT"

BYTE FUNC IsSubstringPrime(INT x BYTE ARRAY primes)
  CHAR ARRAY s(4),tmp(4)
  INT len,start,sub

  IF primes(x)=0 THEN
    RETURN (0)
  FI

  StrI(x,s)
  FOR len=1 TO s(0)-1
  DO
    FOR start=1 TO s(0)-len+1
    DO
      SCopyS(tmp,s,start,start+len-1)
      sub=ValI(tmp)
      IF primes(sub)=0 THEN
        RETURN (0)
      FI
    OD
  OD
RETURN (1)

PROC Main()
  DEFINE MAX="499"
  BYTE ARRAY primes(MAX+1)
  INT i

  Put(125) PutE() ;clear the screen
  Sieve(primes,MAX+1)
  FOR i=2 TO MAX
  DO
    IF IsSubstringPrime(i,primes) THEN
      PrintIE(i)
    FI
  OD
RETURN
Output:

Screenshot from Atari 8-bit computer

2
3
5
7
23
37
53
73
373

ALGOL 68

BEGIN # find primes where all substrings of the digits are prime #
    # find the primes of interest #
    PR read "primes.incl.a68" PR
    []BOOL prime = PRIMESIEVE 500;
    FOR p TO UPB prime DO
        IF prime[ p ] THEN
            INT d := 10;
            BOOL is substring := TRUE;
            WHILE is substring AND d <= UPB prime DO
                INT n := p;
                WHILE is substring AND n > 0 DO
                    is substring := prime[ n MOD d ];
                    n OVERAB 10
                OD;
                d *:= 10
            OD;
            IF is substring THEN print( ( " ", whole( p, 0 ) ) ) FI
        FI
    OD
END
Output:
 2 3 5 7 23 37 53 73 373

ALGOL W

starts with a hardcoded list of 1 digit primes ( 2, 3, 5, 7 ) and constructs the remaining members of the sequence (in order) using the observations that the final digit must be prime and can't be 2 or 5 or the number wouldn't be prime. Additionally, the final digit pair cannot be 33 or 77 as these are divisible by 11.

begin % find primes where every substring of the digits is also priome %
    % sets p( 1 :: n ) to a sieve of primes up to n %
    procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
    begin
        p( 1 ) := false; p( 2 ) := true;
        for i := 3 step 2 until n do p( i ) := true;
        for i := 4 step 2 until n do p( i ) := false;
        for i := 3 step 2 until truncate( sqrt( n ) ) do begin
            integer ii; ii := i + i;
            if p( i ) then for s := i * i step ii until n do p( s ) := false
        end for_i ;
    end Eratosthenes ;
    % it can be shown that all the required primes are under 1000, however we will %
    % not assume this, so we will allow for 4 digit numbers                        %
    integer MAX_NUMBER, MAX_SUBSTRING;
    MAX_NUMBER    := 10000;
    MAX_SUBSTRING := 100; % assume there will be at most 100 such primes           %
    begin
        logical array prime(  1 :: MAX_NUMBER    );
        integer array sPrime( 1 :: MAX_SUBSTRING );
        integer       tCount, sCount, sPos;
        % adds a substring prime to the list %
        procedure addPrime ( integer value p ) ;
        begin
            sCount := sCount + 1;
            sPrime( sCount ) := p;
            writeon( i_w := 1, s_w := 0, " ", p )
        end addPrime ;
        % sieve the primes to MAX_NUMBER %
        Eratosthenes( prime, MAX_NUMBER );
        % clearly, the 1 digit primes are all substring primes %
        sCount := 0;
        for i := 1 until MAX_SUBSTRING do sPrime( i ) := 0;
        for i := 2, 3, 5, 7 do addPrime( i );
        % the subsequent primes can only have 3 or 7 as a final digit as they must end  %
        % with a prime digit and 2 and 5 would mean the number was divisible by 2 or 5  %
        % as all substrings on the prime must also be prime, 33 and 77 are not possible %
        % final digit pairs                                                             %
        sPos := 1;
        while sPrime( sPos ) not = 0 do begin
            integer n3, n7;
            n3 := ( sPrime( sPos ) * 10 ) + 3;
            n7 := ( sPrime( sPos ) * 10 ) + 7;
            if sPrime( sPos ) rem 10 not = 3 and prime( n3 ) then addPrime( n3 );
            if sPrime( sPos ) rem 10 not = 7 and prime( n7 ) then addPrime( n7 );
            sPos := sPos + 1
        end while_sPrime_sPos_ne_0 ;
        write( i_w := 1, s_w := 0, "Found ", sCount, " substring primes" )
    end
end.
Output:
 2 3 5 7 23 37 53 73 373
Found 9 substring primes

AWK

# syntax: GAWK -f SUBSTRING_PRIMES.AWK
# converted from FreeBASIC
BEGIN {
    start = 1
    stop = 500
    for (i=start; i<=stop; i++) {
      if (is_substring_prime(i)) {
        printf("%d ",i)
        count++
      }
    }
    printf("\nSubString Primes %d-%d: %d\n",start,stop,count)
    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 is_substring_prime(n) {
    if (!is_prime(i)) { return(0) }
    if (n < 10) { return(1) }
    if (!is_prime(n%100)) { return(0) }
    if (!is_prime(n%10)) { return(0) }
    if (!is_prime(int(n/10))) { return(0) }
    if (n < 100) { return(1) }
    if (!is_prime(int(n/100))) { return(0) }
    if (!is_prime(int((n%100)/10))) { return(0) }
    return(1)
}
Output:
2 3 5 7 23 37 53 73 373
SubString Primes 1-500: 9


BASIC

BASIC256

function isPrime(v)
    if v < 2 then return False
    if v mod 2 = 0 then return v = 2
    if v mod 3 = 0 then return v = 3
    d = 5
    while d * d <= v
        if v mod d = 0 then return False else d += 2
    end while
    return True
end function

function isSubstringPrime (n)
    if not isPrime(n) then return False
    if n < 10         then return True
    if not isPrime(n mod 100) then return False
    if not isPrime(n mod 10)  then return False
    if not isPrime(n \ 10)    then return False
    if n < 100        then return True
    if not isPrime(n \ 100)   then return False
    if not isPrime((n mod 100) \ 10) then return False
    return True
end function

for i = 1 to 500
    if isSubstringPrime(i) then print i; " ";
next i
end
Output:
Igual que la entrada de FreeBASIC.

PureBasic

Procedure isPrime(v.i)
  If     v <= 1    : ProcedureReturn #False
  ElseIf v < 4     : ProcedureReturn #True
  ElseIf v % 2 = 0 : ProcedureReturn #False
  ElseIf v < 9     : ProcedureReturn #True
  ElseIf v % 3 = 0 : ProcedureReturn #False
  Else
    Protected r = Round(Sqr(v), #PB_Round_Down)
    Protected f = 5
    While f <= r
      If v % f = 0 Or v % (f + 2) = 0
        ProcedureReturn #False
      EndIf
      f + 6
    Wend
  EndIf
  ProcedureReturn #True
EndProcedure

Procedure isSubstringPrime (n)
  If Not isPrime(n) : ProcedureReturn #False
  ElseIf n < 10     : ProcedureReturn #True
  ElseIf Not isPrime(n % 100) : ProcedureReturn #False
  ElseIf Not isPrime(n % 10)  : ProcedureReturn #False
  ElseIf Not isPrime(n / 10)  : ProcedureReturn #False
  ElseIf n < 100    : ProcedureReturn #True
  ElseIf Not isPrime(n / 100) : ProcedureReturn #False
  ElseIf Not isPrime((n % 100)/10) : ProcedureReturn #False
  EndIf
  ProcedureReturn #True
EndProcedure

OpenConsole()
For i.i = 1 To 500
  If isSubstringPrime(i) : Print(Str(i) + " ") : EndIf
Next i
Input()
CloseConsole()
Output:
Igual que la entrada de FreeBASIC.

Yabasic

sub isPrime(v)
    if v < 2 then return False : fi
    if mod(v, 2) = 0 then return v = 2 : fi
    if mod(v, 3) = 0 then return v = 3 : fi
    d = 5
    while d * d <= v
        if mod(v, d) = 0 then return False else d = d + 2 : fi
    wend
    return True
end sub

sub isSubstringPrime (n)
    if not isPrime(n) then return False : fi
    if n < 10 then return True : fi
    if not isPrime(mod(n, 100)) then return False : fi
    if not isPrime(mod(n, 10))  then return False : fi
    if not isPrime(int(n / 10)) then return False : fi
    if n < 100 then return True : fi
    if not isPrime(int(n / 100)) then return False : fi
    if not isPrime(int(mod(n, 100))/10) then return False : fi
    return True
end sub

for i = 1 to 500
    if isSubstringPrime(i) then print i, " "; : fi
next i
end
Output:
Igual que la entrada de FreeBASIC.


C++

#include <iostream>
#include <vector>

std::vector<bool> prime_sieve(size_t limit) {
    std::vector<bool> sieve(limit, true);
    if (limit > 0)
        sieve[0] = false;
    if (limit > 1)
        sieve[1] = false;
    for (size_t i = 4; i < limit; i += 2)
        sieve[i] = false;
    for (size_t p = 3; ; p += 2) {
        size_t q = p * p;
        if (q >= limit)
            break;
        if (sieve[p]) {
            size_t inc = 2 * p;
            for (; q < limit; q += inc)
                sieve[q] = false;
        }
    }
    return sieve;
}

bool substring_prime(const std::vector<bool>& sieve, unsigned int n) {
    for (; n != 0; n /= 10) {
        if (!sieve[n])
            return false;
        for (unsigned int p = 10; p < n; p *= 10) {
            if (!sieve[n % p])
                return false;
        }
    }
    return true;
}

int main() {
    const unsigned int limit = 500;
    std::vector<bool> sieve = prime_sieve(limit);
    for (unsigned int i = 2; i < limit; ++i) {
        if (substring_prime(sieve, i))
            std::cout << i << '\n';
    }
    return 0;
}
Output:
2
3
5
7
23
37
53
73
373

Delphi

Works with: Delphi version 6.0


function IsSubstringPrime(N: integer): boolean;
begin
if not IsPrime(N) then Result:=False
else if n < 10 then Result:=True
else if not IsPrime(N mod 100) then Result:=False
else if not IsPrime(N mod 10) then Result:=False
else if not IsPrime(N div 10) then Result:=False
else if n < 100 then Result:=True
else if not IsPrime(N div 100) then Result:=False
else if not IsPrime((N mod 100) div 10) then Result:=False
else Result:=True;
end;

procedure ShowSubtringPrimes(Memo: TMemo);
var N: integer;
begin
for N:=2 to 500-1 do
 if IsSubstringPrime(N) then Memo.Lines.Add(IntToStr(N));
end;
Output:
2
3
5
7
23
37
53
73
373
Elapsed Time: 8.708 ms.


Factor

For fun, a translation of FreeBASIC.

Translation of: FreeBASIC
Works with: Factor version 0.99 2021-02-05
USING: combinators kernel math math.primes prettyprint sequences ;

:: ssp? ( n -- ? )
    {
        { [ n prime? not ] [ f ] }
        { [ n 10 < ] [ t ] }
        { [ n 100 mod prime? not ] [ f ] }
        { [ n 10 mod prime? not ] [ f ] }
        { [ n 10 /i prime? not ] [ f ] }
        { [ n 100 < ] [ t ] }
        { [ n 100 /i prime? not ] [ f ] }
        { [ n 100 mod 10 /i prime? not ] [ f ] }
        [ t ]
    } cond ;

500 <iota> [ ssp? ] filter .
Output:
V{ 2 3 5 7 23 37 53 73 373 }

FreeBASIC

Since this is limited to one, two, or three-digit numbers I will be a bit cheeky.

#include "isprime.bas"

function is_ssp(n as uinteger) as boolean
    if not isprime(n) then return false
    if n < 10 then return true
    if not isprime(n mod 100) then return false
    if not isprime(n mod 10) then return false
    if not isprime(n\10) then return false
    if n < 100 then return true
    if not isprime(n\100) then return false
    if not isprime( (n mod 100)\10 ) then return false
    return true
end function

for i as uinteger = 1 to 500
    if is_ssp(i) then print i;" ";
next i
print
Output:
2 3 5 7 23 37 53 73 373

Go

Translation of: Wren
Library: Go-rcu

Using a limit

package main

import (
    "fmt"
    "rcu"
)

func main() {
    primes := rcu.Primes(499)
    var sprimes []int
    for _, p := range primes {
        digits := rcu.Digits(p, 10)
        var b1 = true
        for _, d := range digits {
            if !rcu.IsPrime(d) {
                b1 = false
                break
            }
        }
        if b1 {
            if len(digits) < 3 {
                sprimes = append(sprimes, p)
            } else {
                b2 := rcu.IsPrime(digits[0]*10 + digits[1])
                b3 := rcu.IsPrime(digits[1]*10 + digits[2])
                if b2 && b3 {
                    sprimes = append(sprimes, p)
                }
            }
        }
    }
    fmt.Println("Found", len(sprimes), "primes < 500 where all substrings are also primes, namely:")
    fmt.Println(sprimes)
}
Output:
Found 9 primes < 500 where all substrings are also primes, namely:
[2 3 5 7 23 37 53 73 373]


Advanced

package main

import (
    "fmt"
    "rcu"
)

func main() {
    results := []int{2, 3, 5, 7} // number must begin with a prime digit
    odigits := []int{3, 7}       // other digits must be 3 or 7
    var discarded []int
    tests := 4 // i.e. to obtain initial results in the first place

    // check 2 digit numbers or greater
    // note that 'results' is a moving feast. If the loop eventually terminates that's all there are.
    for i := 0; i < len(results); i++ {
        r := results[i]
        for _, od := range odigits {
            // the last digit of r and od must be different otherwise number would be divisible by 11
            if (r % 10) != od {
                n := r*10 + od
                if rcu.IsPrime(n) {
                    results = append(results, n)
                } else {
                    discarded = append(discarded, n)
                }
                tests++
            }
        }
    }
    fmt.Println("There are", len(results), "primes where all substrings are also primes, namely:")
    fmt.Println(results)
    fmt.Println("\nThe following numbers were also tested for primality but found to be composite:")
    fmt.Println(discarded)
    fmt.Println("\nTotal number of primality tests =", tests)
}
Output:
There are 9 primes where all substrings are also primes, namely:
[2 3 5 7 23 37 53 73 373]

The following numbers were also tested for primality but found to be composite:
[27 57 237 537 737 3737]

Total number of primality tests = 15

jq

Works with: jq

Works with gojq, the Go implementation of jq

In the following, we verify that there are only nine "substring primes" as defined for this task..

See e.g. Erdős-primes#jq for a suitable implementation of `is_prime`.

def emit_until(cond; stream): label $out | stream | if cond then break
$out else . end;

def primes:
  2, (range(3;infinite;2) | select(is_prime));

def is_substring(checkPrime):
  def isp: if . == "" then true else tonumber|is_prime end;
  (if checkPrime then is_prime else true end) 
  and (tostring
       | . as $s
       | all(range(0;length) as $i | range($i; length+1) as $j | [$i,$j];
             $s[.[0]:.[1]]|isp ));

# Output an array of the substring primes less than or equal to `.`
def substring_primes:
  . as $n
  | reduce emit_until(. > $n; primes) as $p ( null;
     if $p | is_substring(false)
     then . += [$p]
     else .
     end );

# Input: an array of the substring primes less than or equal to 373.
# Output: any other substring primes.
# Comment: if there are any others, they would have to be constructed
# from the numbers in the input array, as by assumption it includes
# all substring primes less than 100.
def verify:
  . as $sp
  | range(0;length) as $i
  | range(0;length) as $j
  | ([$sp[$i, $j]] | map(tostring) | add | tonumber) as $candidate
  | if $candidate | IN($sp[]) then empty
    elif $candidate | is_substring(true) then $candidate
    else empty
    end;

500 | substring_primes
| "Verifying that the following are the only substring primes:",
  .,
  "...",
  ( [verify] as $extra
    | if $extra == [] then "done" else $extra end )
Output:
Verifying that the following are the only substring primes:
[2,3,5,7,23,37,53,73,373]
...
done


Julia

using Primes

const pmask = primesmask(1, 1000)

function isA085823(n, base = 10, sieve = pmask)
    dig = digits(n; base=base)
    for i in 1:length(dig), j in i:length(dig)
        k = evalpoly(base, dig[i:j])
        (k == 0 || !sieve[k]) && return false
    end
    return true
end

println(filter(isA085823, 1:1000))
Output:
[2, 3, 5, 7, 23, 37, 53, 73, 373]

Advanced task

using Primes

const nt, nons = [0], Int[]

counted_primetest(n) = (nt[1] += 1; b = isprime(n); !b && push!(nons, n); b) 

# start with 1 digit primes
const results = [2, 3, 5, 7]

# check 2 digit candidates
for n in results, i in [3, 7]
    if n != i
        candidate = n * 10 + i
        candidate < 100 && counted_primetest(candidate) && push!(results, candidate)
    end
end

# check 3 digit candidates
for n in results, i in [3, 7]
    if 10 < n < 100 && n % 10 != i
        candidate = n * 10 + i
        counted_primetest(candidate) && push!(results, candidate)
    end
end

println("Results: $results.\nThe function isprime() was called $(nt[1]) times.")
println("Discarded candidates: ", nons)

# Because 237, 537, and 737 are already excluded, we cannot generate any larger candidates from 373.
Output:
Results: [2, 3, 5, 7, 23, 37, 53, 73, 373].
The function isprime() was called 10 times.
Discarded candidates: [27, 57, 237, 537, 737]

Mathematica /Wolfram Language

Select[Range[500], PrimeQ[#] && AllTrue[Subsequences[IntegerDigits[#], {1, \[Infinity]}], FromDigits /* PrimeQ] &]
Output:
{2, 3, 5, 7, 23, 37, 53, 73, 373}

Nim

The algorithm we use solves the advanced task as it finds the substring primes with only 11 primality tests. Note that, if we limit to numbers with at most three digits, 10 tests are sufficient. As we don’t use this limitation, we need one more test to detect than 3737 is not prime.

import sequtils, strutils

type
  Digit = 0..9
  DigitSeq = seq[Digit]


func isOddPrime(n: Positive): bool =
  ## Check if "n" is an odd prime.
  assert n > 10
  var d = 3
  while d * d <= n:
    if n mod d == 0: return false
    inc d, 2
  return true


func toInt(s: DigitSeq): int =
  ## Convert a sequence of digits to an int.
  for d in s:
    result = 10 * result + d


var result = @[2, 3, 5, 7]
var list: seq[DigitSeq] = result.mapIt(@[Digit it])
var primeTestCount = 0

while list.len != 0:
  var newList: seq[DigitSeq]
  for dseq in list:
    for d in [Digit 3, 7]:
      if dseq[^1] != d:   # New digit must be different of last digit.
        inc primeTestCount
        let newDseq = dseq & d
        let candidate = newDseq.toInt
        if candidate.isOddPrime:
          newList.add newDseq
          result.add candidate
  list = move(newList)

echo "List of substring primes: ", result.join(" ")
echo "Number of primality tests: ", primeTestCount
Output:
List of substring primes: 2 3 5 7 23 37 53 73 373
Number of primality tests: 11

Perl

#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Substring_primes
use warnings;

my %prime;

LOOP:
for (2 .. 500 )
  {
  my %substrings =  ();
  /.+(?{ $prime{$&} or $substrings{$&}++ })(*FAIL)/;
  for my $try ( sort { $a <=> $b } keys %substrings )
    {
    $try < 2 and next LOOP;
    $prime{$try} || (1 x $try) !~ /^(11+)\1+$/ ? $prime{$try}++ : next LOOP;
    }
  }
printf "  %d" x %prime . "\n", sort {$a <=> $b} keys %prime;
Output:
 2  3  5  7  23  37  53  73  373


Phix

This tests a total of just 15 numbers for primality.

with javascript_semantics
--sequence tested = {}
--function a085823(integer p=0)
--  sequence res={}
function a085823(sequence res={}, tested={}, integer p=0)
    for i=(p!=0)+1 to 4 do
        integer t = get_prime(i)
        if t!=remainder(p,10) and (p=0 or t!=5) then
            t += p*10
            if is_prime(t) then
--              {res,tested} = a085823(res&t,tested,t)
                {res,tested} = a085823(deep_copy(res)&t,deep_copy(tested),t)    -- [1]
--              res &= t
--              res &= a085823(t)
            else
                tested &= t
            end if
        end if
    end for
    return {res,tested}
--  return res
end function
sequence {res,tested} = a085823()  -- sort() if you prefer...
--sequence res = a085823()  -- sort() if you prefer...
printf(1,"There are %d such A085823 primes: %V\n",{length(res),res})
printf(1,"%d innocent bystanders falsly accused of being prime (%d tests in total): %V\n",
        {length(tested),length(tested)+length(res),tested})

[1]It is possible that the compiler could be improved to avoid the need for those deep_copy().
The other seven commented out lines show a different way to avoid any use of deep_copy().

Output:
There are 9 such A085823 primes: {2,23,3,37,373,5,53,7,73}
6 innocent bystanders falsly accused of being prime (15 tests in total): {237,27,3737,537,57,737}

Picat

Checking via substrings

% get all the substrings of a number
subs(N) = findall(S, (append(_Pre,S,_Post,N.to_string), S.len > 0) ).

go =>
  Ps = [],
  foreach(Prime in primes(500))
    (foreach(N in subs(Prime) prime(N) end -> Ps := Ps ++ [Prime] ; true)
  end,
  println(Ps).
Output:
[2,3,5,7,23,37,53,73,373]

Checking via predicate

Translation of: AWK

Here we must use cut (!) to ensure that the test does not continue after a satisfied test. This is a "red cut" (i.e. removing it would change the logic of the program) and these should be avoided if possible.

t(N,false) :-
  not prime(N),!.
t(N,true) :-
  N < 10,!.
t(N,false) :-
  not prime(N mod 100), !.
t(N,false) :-
  not prime(N mod 10),!.
t(N,false) :-
  not prime(N // 10),!.
t(N,true) :-
  N < 100,!.
t(N,false) :-
  not prime(N // 100),!.
t(N,false) :-
  not prime((N mod 100) // 10),!.
t(_N,true).

go2 =>
  println(findall(N,(member(N,1..500),t(N,Status),Status==true))).
Output:
[2,3,5,7,23,37,53,73,373]


Raku

my @p = (^10).grep: *.is-prime;

say gather while @p {
    .take for @p;

    @p = ( @p X~ <3 7> ).grep: { .is-prime and .substr(*-2,2).is-prime }
}
Output:
(2 3 5 7 23 37 53 73 373)

Stretch Goal

my $prime-tests = 0;
my @non-primes;
sub spy-prime ($n) {
    $prime-tests++;
    my $is-p = $n.is-prime;

    push @non-primes, $n unless $is-p;
    return $is-p;
}

my @p = <2 3 5 7>;

say gather while @p {
    .take for @p;

    @p = ( @p X~ <3 7> ).grep: { !.ends-with(33|77) and .&spy-prime };
}
.say for :$prime-tests, :@non-primes;
Output:
(2 3 5 7 23 37 53 73 373)
prime-tests => 11
non-primes => [27 57 237 537 737 3737]

REXX

/*REXX program finds/shows decimal primes where all substrings are also prime,  N < 500.*/
parse arg n cols .                               /*obtain optional argument from the CL.*/
if    n=='' |    n==","  then    n= 500          /*Not specified?  Then use the default.*/
if cols=='' | cols==","  then cols=  10          /* "      "         "   "   "     "    */
call genP                                        /*build array of semaphores for primes.*/
w= 10                                            /*width of a number in any column.     */
title= ' primes (base ten) where all substrings are also primes, where  N  < '  commas(n)
say ' index │'center(title, 1 + cols*(w+1)     ) /*display the   title   of the output. */
say '───────┼'center(""   , 1 + cols*(w+1), '─') /*   "     "  separator  "  "     "    */
found= 0;                                 idx= 1 /*define # substring primes found; IDX.*/
$=                                               /*a list of substring primes (so far). */
     do j=1  for #;   p= @.j;  p2= substr(p, 2)  /*search for primes that fit criteria. */
     if verify(p,  014689, 'M')>0  then iterate  /*does it contain any of these digits? */
     if verify(p2, 25    , 'M')>0  then iterate  /*  "  P2    "     "   "   "     "     */
                        L= length(p)             /*obtain the length of the   P   prime.*/
         do   k=1   for L-1                      /*test for primality for all substrings*/
           do m=k+1 to  L;  y= substr(p, k, m-1) /*extract a substring from the P prime.*/
           if \!.y  then iterate j               /*does substring of P  not prime? Skip.*/
           end   /*m*/
         end     /*k*/

     found= found + 1                            /*bump the number of substring primes. */
     $= $  right( commas(p), w)                  /*add a substring prime  ──►  $  list. */
     if found//cols\==0  then iterate            /*have we populated a line of output?  */
     say center(idx, 7)'│'  substr($, 2);   $=   /*display what we have so far  (cols). */
     idx= idx + cols                             /*bump the  index  count for the output*/
     end   /*j*/

if $\==''  then say center(idx, 7)'│'  substr($, 2)      /*display any residual numbers.*/
say '───────┴'center(""   , 1 + cols*(w+1), '─')         /*   "     a  foot separator.  */
say;            say 'Found '       words($)      title   /*   "    the summary.         */
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?;  do jc=length(?)-3  to 1  by -3; ?=insert(',', ?, jc); end;  return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: !.= 0                                      /*placeholders for primes (semaphores).*/
      @.1=2;  @.2=3;  @.3=5;  @.4=7;  @.5=11     /*define some low primes.              */
      !.2=1;  !.3=1;  !.5=1;  !.7=1;  !.11=1     /*   "     "   "    "     flags.       */
                        #=5;     s.#= @.# **2    /*number of primes so far;     prime². */
                                                 /* [↓]  generate more  primes  ≤  high.*/
        do j=@.#+2  by 2  to n-1                 /*find odd primes from here on.        */
        parse var j '' -1 _;       if    _==5  then iterate   /*J ÷ by 5?  (right digit)*/
        if j//3==0  then iterate;  if j//7==0  then iterate   /*" "  " 3?;   J ÷ by 7?  */
               do k=5  while s.k<=j              /* [↓]  divide by the known odd primes.*/
               if j // @.k == 0  then iterate j  /*Is  J ÷ X?  Then not prime.     ___  */
               end   /*k*/                       /* [↑]  only process numbers  ≤  √ J   */
        #= #+1;    @.#= j;    s.#= j*j;   !.j= 1 /*bump # of Ps; assign next P;  P²; P# */
        end          /*j*/;               return
output   when using the default inputs:
 index │                    primes (base ten) where all substrings are also primes, where  N  <  500
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │          2          3          5          7         23         37         53         73        373
───────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────

Found  9  primes (base ten) where all substrings are also primes, where  N  <  500

Ring

load "stdlib.ring"

see "working..." + nl
see "Numbers in which all substrings are primes:" + nl

row = 0
limit1 = 500

for n = 1 to limit1
    flag = 1
    strn = string(n)
    for m = 1 to len(strn)
        for p = 1 to len(strn)
            temp = substr(strn,m,p)
            if temp != ""
                if isprime(number(temp))
                   flag = 1
                else
                   flag = 0
                   exit 2
                ok
            ok
         next
      next
      if flag = 1
         see "" + n + " "
      ok 
next

see nl + "Found " + row + " numbers in which all substrings are primes" + nl
see "done..." + nl
Output:
working...
Numbers in which all substrings are primes:
2 3 5 7 23 37 53 73 373 
Found 9 numbers in which all substrings are primes
done...

Rust

use primes::is_prime;

fn counted_prime_test() {
    let mut number_of_prime_tests = 0;
    let mut non_primes = vec![0; 0];
    // start with 1 digit primes
    let mut results: Vec<i32> = [2, 3, 5, 7].to_vec();
    // check 2 digit candidates
    for n in results.clone() {
        for i in [3, 7].to_vec() {
            if n != i {
                let candidate = n * 10 + i;
                if candidate < 100 {
                    number_of_prime_tests += 1;
                    if is_prime(candidate as u64) {
                        results.push(candidate);
                    } else {
                        non_primes.push(candidate);
                    }
                }
            }
        }
    }
    // check 3 digit candidates
    for n in results.clone() {
        for i in [3, 7].to_vec() {
            if 10 < n && n < 100 && n % 10 != i {
                let candidate = n * 10 + i;
                number_of_prime_tests += 1;
                if is_prime(candidate as u64) {
                    results.push(candidate);
                } else {
                    non_primes.push(candidate);
                }
            }
        }
    }
    println!("Results: {results:?}.\nThe function isprime() was called {number_of_prime_tests} times.");
    println!("Discarded nonprime candidates: {non_primes:?}");
    println!("Because 237, 537, and 737 are excluded, we cannot generate any larger candidates from 373.");
}

fn main() {
    counted_prime_test();
}
Output:
Results: [2, 3, 5, 7, 23, 37, 53, 73, 373].
The function isprime() was called 10 times.
Discarded nonprime candidates: [27, 57, 237, 537, 737]
Because 237, 537, and 737 are already excluded, we cannot generate any larger candidates from 373.

RPL

≪ { 2 3 5 7 } { } 0 1 → winners losers tests index
  ≪ 3
     DO
        winners index GET 10 * OVER + SWAP
        IF 7 == THEN 3 'index' 1 STO+ ELSE 7 END
        SWAP 1 CF
        IF DUP 3 MOD OVER 100 MOD 11 MOD AND THEN  
           IF DUP ISPRIME? 'tests' 1 STO+ 1 FS THEN 
              IF DUP 100 MOD ISPRIME? 'tests' 1 STO+ 1 FS THEN 'winners' OVER STO+ 1 CF 
        END END END
        IF 1 FS? THEN 'losers' OVER STO+ END
     UNTIL 500 > END
     DROP winners losers tests
≫ ≫ 'A085823' STO
Output:
3: { 2 3 5 7 23 37 53 73 373 }
2: { }
1: 10

Sidef

Generic solution for any base >= 2.

func split_at_indices(array, indices) {

    var parts = []
    var i = 0

    for j in (indices) {
        parts << [array[i..j]]
        i = j+1
    }

    parts
}

func consecutive_partitions(array, callback) {
    for k in (0..array.len) {
        combinations(array.len, k, {|*indices|
            var t = split_at_indices(array, indices)
            if (t.sum_by{.len} == array.len) {
                callback(t)
            }
        })
    }
}

func is_substring_prime(digits, base) {

    for k in (^digits) {
        digits.first(k+1).digits2num(base).is_prime || return false
    }

    consecutive_partitions(digits, {|part|
        part.all { .digits2num(base).is_prime } || return false
    })

    return true
}

func generate_from_prefix(p, base, digits) {

    var seq = [p]

    for d in (digits) {
        var t = [d, p...]
        if (is_prime(t.digits2num(base)) && is_substring_prime(t, base)) {
            seq << __FUNC__(t, base, digits)...
        }
    }

    return seq
}

func substring_primes(base) {     # finite sequence for each base >= 2

    var prime_digits = (base-1 -> primes)   # prime digits < base

    prime_digits.map  {|p| generate_from_prefix([p], base, prime_digits)... }\
                .map  {|t| digits2num(t, base) }\
                .sort
}

for base in (2..20) {
    say "base = #{base}: #{substring_primes(base)}"
}
Output:
base = 2: []
base = 3: [2]
base = 4: [2, 3, 11]
base = 5: [2, 3, 13, 17, 67]
base = 6: [2, 3, 5, 17, 23]
base = 7: [2, 3, 5, 17, 19, 23, 37]
base = 8: [2, 3, 5, 7, 19, 23, 29, 31, 43, 47, 59, 61, 157, 239, 251, 349, 379, 479, 491]
base = 9: [2, 3, 5, 7, 23, 29, 47]
base = 10: [2, 3, 5, 7, 23, 37, 53, 73, 373]
base = 11: [2, 3, 5, 7, 29, 79]
base = 12: [2, 3, 5, 7, 11, 29, 31, 41, 43, 47, 67, 71, 89, 137, 139, 359, 499, 503, 521, 569, 571, 809, 857, 859, 6043]
base = 13: [2, 3, 5, 7, 11, 29, 31, 37, 41, 67, 379]
base = 14: [2, 3, 5, 7, 11, 13, 31, 41, 47, 53, 73, 83, 101, 103, 109, 157, 167, 193, 439, 661, 1033, 2203]
base = 15: [2, 3, 5, 7, 11, 13, 37, 41, 43, 47, 107, 167, 197, 557, 617, 647]
base = 16: [2, 3, 5, 7, 11, 13, 37, 43, 53, 59, 61, 83, 179, 181, 211, 691, 947, 3389]
base = 17: [2, 3, 5, 7, 11, 13, 37, 41, 47, 53, 223, 631]
base = 18: [2, 3, 5, 7, 11, 13, 17, 41, 43, 47, 53, 59, 61, 67, 71, 97, 101, 103, 107, 131, 137, 139, 211, 239, 241, 251, 311, 313, 317, 751, 787, 859, 1069, 1103, 1109, 1213, 1223, 1283, 1289, 1759, 1831, 1861, 1871, 1931, 1933, 2371, 3803, 4349, 4523, 5639, 5647, 15467, 19867, 34807]
base = 19: [2, 3, 5, 7, 11, 13, 17, 41, 43, 59, 97, 211]
base = 20: [2, 3, 5, 7, 11, 13, 17, 19, 43, 47, 53, 59, 67, 71, 73, 79, 103, 107, 113, 151, 157, 223, 227, 233, 239, 263, 271, 277, 347, 353, 359, 383, 397, 1063, 1423, 1427, 1433, 1439, 1471, 1583, 1597, 3023, 4663, 4783, 5273, 5279, 7673, 28663]

Wren

Library: Wren-math

Using a limit

import "./math" for Int
var primes = Int.primeSieve(499)
var sprimes = []
for (p in primes) {
    var digits = Int.digits(p)
    var b1 = digits.all { |d| Int.isPrime(d) }
    if (b1) {
        if (digits.count < 3) {
            sprimes.add(p)
        } else {
            var b2 = Int.isPrime(digits[0] * 10 + digits[1])
            var b3 = Int.isPrime(digits[1] * 10 + digits[2])
            if (b2 && b3) sprimes.add(p)
        }
    }
}
System.print("Found %(sprimes.count) primes < 500 where all substrings are also primes, namely:")
System.print(sprimes)
Output:
Found 9 primes < 500 where all substrings are also primes, namely:
[2, 3, 5, 7, 23, 37, 53, 73, 373]

Advanced

This follows the logic in the OEIS A085823 comments.

import "./math" for Int

var results = [2, 3, 5, 7] // number must begin with a prime digit
var odigits = [3, 7]       // other digits must be 3 or 7 as there would be a composite substring otherwise
var discarded = []
var tests = 4 // i.e. to obtain initial results in the first place

// check 2 digit numbers or greater
// note that 'results' is a moving feast. If the loop eventually terminates that's all there are.
for (r in results) {
    for (od in odigits) {
        // the last digit of r and od must be different otherwise number would be divisible by 11
        if ((r % 10) != od) {
            var n = r * 10 + od
            if (Int.isPrime(n)) results.add(n) else discarded.add(n)
            tests = tests + 1
        }
    }
}

System.print("There are %(results.count) primes where all substrings are also primes, namely:")
System.print(results)
System.print("\nThe following numbers were also tested for primality but found to be composite:")
System.print(discarded)
System.print("\nTotal number of primality tests = %(tests)")
Output:
There are 9 primes where all substrings are also primes, namely:
[2, 3, 5, 7, 23, 37, 53, 73, 373]

The following numbers were also tested for primality but found to be composite:
[27, 57, 237, 537, 737, 3737]

Total number of primality tests = 15

XPL0

func IsPrime(N);        \Return 'true' if N is a prime number
int  N, I;
[if N <= 1 then return false;
for I:= 2 to sqrt(N) do
    if rem(N/I) = 0 then return false;
return true;
];

int Digit, Huns, Tens, Ones, N;
[Digit:= [0, 2, 3, 5, 7];       \leading zeros are ok
for Huns:= 0 to 4 do
  for Tens:= 0 to 4 do
    if Huns+Tens=0 or IsPrime(Digit(Huns)*10+Digit(Tens)) then
      for Ones:= 1 to 4 do      \can't end in 0
        [N:= Digit(Huns)*100 + Digit(Tens)*10 + Digit(Ones);
        if N<500 & IsPrime(N) & IsPrime(Digit(Tens)*10+Digit(Ones)) then
          [IntOut(0, N);  ChOut(0, ^ )];
        ];
]
Output:
2 3 5 7 23 37 53 73 373