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.

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

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

Output:
 2 3 5 7 23 37 53 73 373
Found 9 substring primes

AWK

<lang AWK>

  1. syntax: GAWK -f SUBSTRING_PRIMES.AWK
  2. 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)

} </lang>

Output:
2 3 5 7 23 37 53 73 373
SubString Primes 1-500: 9

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

FreeBASIC

Since this is limited to one, two, or three-digit numbers I will be a bit cheeky. <lang freebasic>#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</lang>

Output:
2 3 5 7 23 37 53 73 373

Julia

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

</lang>

Output:
[2, 3, 5, 7, 23, 37, 53, 73, 373]

Advanced task

<lang julia>using Primes

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

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

  1. start with 1 digit primes

const results = [2, 3, 5, 7]

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

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

  1. Because 237, 537, and 737 are already excluded, we cannot generate any larger candidates from 373.

</lang>

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]

Perl

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

Output:
 2  3  5  7  23  37  53  73  373


Phix

This tests a total of just 15 numbers for primality. 

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)
            else
                tested &= t
            end if
        end if
    end for
    return {res,tested}
end function
sequence {res,tested} = 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})
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}

Raku

<lang perl6>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 }

}</lang>

Output:
(2 3 5 7 23 37 53 73 373)

Stretch Goal

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

Output:
(2 3 5 7 23 37 53 73 373)
prime-tests => 11
non-primes => [27 57 237 537 737 3737]

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; ptests= 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

Using a limit

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

Advanced

This follows the logic in the OEIS A085823 comments. <lang ecmascript>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)")</lang>

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
Retrieved from "https://rosettacode.org/wiki/Substring_primes?oldid=310975"