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

C++

<lang cpp>#include <iostream>

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

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

Wren

Library: Wren-math

<lang ecmascript>import "/math" for Int

var getDigits = Fn.new { |n|

   var digits = []
   while (n > 0) {
       digits.add(n%10)
       n = (n/10).floor
   }
   return digits[-1..0]

}

var primes = Int.primeSieve(499) var sprimes = [] for (p in primes) {

   var digits = getDigits.call(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)</lang>

Output:

Found 9 primes < 500 where all substrings are also primes, namely:
[2, 3, 5, 7, 23, 37, 53, 73, 373]