Substring primes

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

Primes   (in base ten)   in which all substrings are also primes,   where   n  <  500

ALGOL 68

<lang algol68>BEGIN # find primes where all substrings of the digits are prime #

   # reurns a sieve of primes up to n #
   PROC sieve = ( INT n )[]BOOL:
        BEGIN
           [ 1 : n ]BOOL p;
           p[ 1 ] := FALSE; p[ 2 ] := TRUE;
           FOR i FROM 3 BY 2 TO n DO p[ i ] := TRUE  OD;
           FOR i FROM 4 BY 2 TO n DO p[ i ] := FALSE OD;
           FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO
               IF p[ i ] THEN FOR s FROM i * i BY i + i TO n DO p[ s ] := FALSE OD FI
           OD;
           p
        END # prime list # ;
   # find the primes of interest #
   INT max number = 500;
   []BOOL prime = sieve( max number );
   FOR p TO UPB prime DO
       IF prime[ p ] THEN
           INT d := 10;
           BOOL is substring := TRUE;
           WHILE is substring AND d <= max number DO
               INT n := p;
               WHILE is substring AND n > 0 DO
                   INT sub digits = n MOD d;
                   is substring := IF sub digits = 0 THEN FALSE ELSE prime[ sub digits ] FI;
                   n OVERAB 10
               OD;
               d *:= 10
           OD;
           IF is substring THEN print( ( " ", whole( p, 0 ) ) ) FI
       FI
   OD

END</lang>

Output:

 2 3 5 7 23 37 53 73 373

REXX

<lang rexx>/*REXX program finds/shows decimal primes where all substrings are also prime, N < 500.*/ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 500 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 7 /*width of a number in any column. */

         @sprs= ' primes (base ten) where all substrings are also primes  < '       hi

say ' index │'center(@sprs, 1 + cols*(w+1) ) /*display the title of the output. */ say '───────┼'center("" , 1 + cols*(w+1), '─') /* " " separator " " " */ $= /*a list of substring primes (so far). */

    do j=1  for #;   x= @.j;  x2= substr(x, 2)  /*search for primes that fit criteria. */
    if verify(x,  014689, 'M')>0  then iterate  /*does X  prime have any of these digs?*/
    if verify(x2, 25    , 'M')>0  then iterate  /*  "  X2  part  "    "   "   "     "  */
                       L= length(x)             /*obtain the length of the   X   prime.*/
        do   k=1   for L-1                      /*test for primality for all substrings*/
          do m=k+1 to  L;  y= substr(x, k, m-1) /*extract a substring from the X prime.*/
          if \!.y  then iterate j               /*does substring of X  not prime? Skip.*/
          end   /*m*/
        end     /*k*/

    $= $  right(x, w)                           /*add the  X  prime to the   $   list. */
    end   /*j*/

if $\== then say center(1,7)"│" substr($, 2) /*display the list of substring primes.*/ say say 'Found ' words($) @sprs exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ 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 hi                  /*find odd primes from here on.        */
       parse var j  -1 _; if     _==5  then iterate  /*J divisible by 5?  (right dig)*/
                            if j// 3==0  then iterate  /*"     "      " 3?             */
                            if j// 7==0  then iterate  /*"     "      " 7?             */
                                                /* [↑]  the above  3  lines saves time.*/
              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</lang>

output   when using the default inputs:

 index │          primes (base ten) where all substrings are also primes  <  500
───────┼─────────────────────────────────────────────────────────────────────────────────
   1   │       2       3       5       7      23      37      53      73     373

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

Ring

<lang 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 </lang>

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...