Substring primes: Difference between revisions

← Older edit

Substring primes (view source)

Revision as of 16:48, 10 February 2024

30,548 bytes added , 3 months ago

m

→‎{{header|Wren}}: Minor tidy

PureFox

9,476

edits

Revision as of 09:50, 6 April 2021 (view source) Petelomax (talk \| contribs) (Reduced tests to 11) ← Older edit		Latest revision as of 16:48, 10 February 2024 (view source) PureFox (talk \| contribs) m (→‎{{header\|Wren}}: Minor tidy)
(47 intermediate revisions by 22 users not shown)
Line 4: ;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. <br><br> ;Advanced: Solve by testing at most 1115 numbers for primality. Show a list of all numbers tested that were not prime. <br><br> =={{header\|11l}}== {{trans\|Go}} <syntaxhighlight lang="11l">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)</syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|Action!}}== {{libheader\|Action! Sieve of Eratosthenes}} <syntaxhighlight lang="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</syntaxhighlight> {{out}} [https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Substring_primes.png Screenshot from Atari 8-bit computer] <pre> 2 3 5 7 23 37 53 73 373 </pre> =={{header\|ALGOL 68}}== {{libheader\|ALGOL 68-primes}} ~~<lang algol68>BEGIN # find primes where all substrings of the digits are prime #~~ <syntaxhighlight 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 # PR read "primes.incl.a68" PR ~~INT max number = 500;~~ []BOOL prime = ~~sieve(~~PRIMESIEVE ~~max number )~~500; FOR p TO UPB prime DO IF prime[ p ] THEN INT d := 10; BOOL is substring := TRUE; WHILE is substring AND d <= ~~max~~UPB ~~number~~prime DO INT n := p; WHILE is substring AND n > 0 DO ~~INT~~is ~~sub digits~~substring := prime[ n MOD d ]; ~~is substring := IF sub digits = 0 THEN FALSE ELSE prime[ sub digits ] FI;~~ n OVERAB 10 OD; Line 43 ⟶ 135: FI OD END</~~lang~~syntaxhighlight> {{out}} <pre> 2 3 5 7 23 37 53 73 373 </pre> =={{header\|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. <syntaxhighlight 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.</syntaxhighlight> {{out}} <pre> 2 3 5 7 23 37 53 73 373 Found 9 substring primes </pre> =={{header\|AWK}}== <syntaxhighlight lang="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) } </syntaxhighlight> {{out}} <pre> 2 3 5 7 23 37 53 73 373 SubString Primes 1-500: 9 </pre> =={{header\|BASIC}}== ==={{header\|BASIC256}}=== <syntaxhighlight lang="freebasic">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</syntaxhighlight> {{out}} <pre> Igual que la entrada de FreeBASIC. </pre> ==={{header\|PureBasic}}=== <syntaxhighlight lang="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()</syntaxhighlight> {{out}} <pre> Igual que la entrada de FreeBASIC. </pre> ==={{header\|Yabasic}}=== <syntaxhighlight lang="freebasic">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</syntaxhighlight> {{out}} <pre> Igual que la entrada de FreeBASIC. </pre> =={{header\|C++}}== <~~lang~~syntaxhighlight lang="cpp">#include <iostream> #include <vector> Line 94 ⟶ 401: } return 0; }</~~lang~~syntaxhighlight> {{out}} Line 108 ⟶ 415: 373 </pre> =={{header\|Delphi}}== {{works with\|Delphi\|6.0}} {{libheader\|SysUtils,StdCtrls}} <syntaxhighlight lang="Delphi"> 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; </syntaxhighlight> {{out}} <pre> 2 3 5 7 23 37 53 73 373 Elapsed Time: 8.708 ms. </pre> =={{header\|Factor}}== For fun, a translation of FreeBASIC. {{trans\|FreeBASIC}} {{works with\|Factor\|0.99 2021-02-05}} <syntaxhighlight lang="factor">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 .</syntaxhighlight> {{out}} <pre> V{ 2 3 5 7 23 37 53 73 373 } </pre> =={{header\|FreeBASIC}}== Since this is limited to one, two, or three-digit numbers I will be a bit cheeky. <syntaxhighlight 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</syntaxhighlight> {{out}}<pre>2 3 5 7 23 37 53 73 373</pre> =={{header\|Go}}== {{trans\|Wren}} {{libheader\|Go-rcu}} ===Using a limit=== <syntaxhighlight lang="go">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) }</syntaxhighlight> {{out}} <pre> Found 9 primes < 500 where all substrings are also primes, namely: [2 3 5 7 23 37 53 73 373] </pre> <br> ===Advanced=== <syntaxhighlight lang="go">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 := r10 + 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) }</syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|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%C5%91s-primes#jq]] for a suitable implementation of `is_prime`. <syntaxhighlight lang="jq">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 )</syntaxhighlight> {{out}} <pre> Verifying that the following are the only substring primes: [2,3,5,7,23,37,53,73,373] ... done </pre> =={{header\|Julia}}== <~~lang~~syntaxhighlight lang="julia">using Primes const pmask = primesmask(1, 1000) Line 124 ⟶ 678: println(filter(isA085823, 1:1000)) </~~lang~~syntaxhighlight>{{out}} <pre> [2, 3, 5, 7, 23, 37, 53, 73, 373] </pre> === Advanced task === <syntaxhighlight lang="julia">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. </syntaxhighlight>{{out}} <pre> Results: [2, 3, 5, 7, 23, 37, 53, 73, 373]. The function isprime() was called 10 times. Discarded candidates: [27, 57, 237, 537, 737] </pre> =={{header\|Mathematica}}/{{header\|Wolfram Language}}== <syntaxhighlight lang="mathematica">Select[Range[500], PrimeQ[#] && AllTrue[Subsequences[IntegerDigits[#], {1, \[Infinity]}], FromDigits /* PrimeQ] &]</syntaxhighlight> {{out}} <pre>{2, 3, 5, 7, 23, 37, 53, 73, 373}</pre> =={{header\|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. <syntaxhighlight lang="nim">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</syntaxhighlight> {{out}} <pre>List of substring primes: 2 3 5 7 23 37 53 73 373 Number of primality tests: 11</pre> =={{header\|Perl}}== <syntaxhighlight 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;</syntaxhighlight> {{out}} 2 3 5 7 23 37 53 73 373 =={{header\|Phix}}== ~~There is no need for a limit of 500.~~ This tests a total of just 1115 numbers for primality. <!--<~~lang~~syntaxhighlight ~~Phix~~lang="phix">(phixonline)--> <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> <span style="color: #000080;font-style:italic;">--sequence tested = {} --function a085823(integer p=0) -- sequence res={}</span> <span style="color: #008080;">function</span> <span style="color: #000000;">a085823</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">={},</span> <span style="color: #000000;">tested</span><span style="color: #0000FF;">={},</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">34</span> <span style="color: #008080;">do</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #~~0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000~~7060A8;">7get_prime</span><span style="color: #0000FF;">}[(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">if</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">!=</span><span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;"></span><span style="color: #000000;">10</span> <span style="color: #008080;">if</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- {res,tested} = a085823(res&t,tested,t)</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a085823</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">&</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a085823</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">),</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- [1] -- res &= t -- res &= a085823(t)</span> <span style="color: #008080;">else</span> <span style="color: #000000;">tested</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">t</span> Line 145 ⟶ 821: <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- return res</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> <span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a085823</span><span style="color: #0000FF;">()</span> <span style="color: #000080;font-style:italic;">-- sort() if you prefer...~~</span>~~ --sequence res = a085823() -- sort() if you prefer...</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"There are %d such A085823 primes: %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #000000;">res</span><span style="color: #0000FF;">})</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d innocent bystanders falsly accused of being prime (%d tests in total): %V\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">)+</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">})</span> <!--</~~lang~~syntaxhighlight>--> <small>[1]It is possible that the compiler could be improved to avoid the need for those deep_copy().</small><br> <small>The other seven commented out lines show a different way to avoid any use of deep_copy().</small> {{out}} <pre> There are 79 such A085823 primes: {2,23,3,37,373,5,53,7,73} 46 innocent bystanders falsly accused of being prime (1115 tests in total): {237,27,3737,537,57,737} </pre> =={{header\|Picat}}== ===Checking via substrings=== <syntaxhighlight lang="picat">% 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).</syntaxhighlight> {{out}} <pre>[2,3,5,7,23,37,53,73,373]</pre> ===Checking via predicate=== {{trans\|AWK}} Here we must use cut (<code>!</code>) 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. <syntaxhighlight lang="picat">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))).</syntaxhighlight> {{out}} <pre>[2,3,5,7,23,37,53,73,373]</pre> =={{header\|Raku}}== <syntaxhighlight lang="raku" line>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 } }</syntaxhighlight> {{out}} <pre> (2 3 5 7 23 37 53 73 373)</pre> ===Stretch Goal=== <syntaxhighlight lang="raku" line>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;</syntaxhighlight> {{out}} <pre> (2 3 5 7 23 37 53 73 373) prime-tests => 11 non-primes => [27 57 237 537 737 3737]</pre> =={{header\|REXX}}== <~~lang~~syntaxhighlight lang="rexx">/REXX program finds/shows decimal primes where all substrings are also prime, N < 500./ parse arg hin cols . /obtain optional argument from the CL./ if hi n=='' \| hi n=="," then hi n= 500 /Not specified? Then use the default./ if cols=='' \| cols=="," then cols= 10 /* " " " " " " / call genP /build array of semaphores for primes./ w= 7 10 /width of a number in any column. / ~~@sprs~~title= ' primes (base ten) where all substrings are also primes, where < 'N < ' hicommas(n) say ' index │'center(~~@sprs~~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 #; xp= @.j; x2p2= substr(xp, 2) /search for primes that fit criteria. / if verify(xp, 014689, 'M')>0 then iterate /does Xit ~~prime have~~contain any of these ~~digs~~digits? / if verify(x2p2, 25 , 'M')>0 then iterate / " X2P2 ~~part~~ " " " " " / L= length(xp) /obtain the length of the XP prime./ do k=1 for L-1 /test for primality for all substrings/ do m=k+1 to L; y= substr(xp, k, m-1) /extract a substring from the XP prime./ if \!.y then iterate j /does substring of XP not prime? Skip./ end /m/ end /k/ $found= $found + ~~right(x,~~1 w) /~~add~~bump the number Xof substring ~~prime to the $ list~~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(1idx, 7)"'│"' substr($, 2) /display ~~the list of~~any ~~substring~~residual ~~primes~~numbers./ say '───────┴'center("" , 1 + cols(w+1), '─') /* " a foot separator. / ~~say~~ say; say 'Found ' words($) title / " the summary. ~~@sprs~~/ 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)./ Line 191 ⟶ 957: #=5; s.#= @.# 2 /number of primes so far; prime². / / [↓] generate more primes ≤ high./ do j=@.#+2 by 2 to hi n-1 /find odd primes from here on. / parse var j '' -1 _; if if _==5 then iterate /J ~~divisible~~÷ by 5? (right ~~dig~~digit)/ if j//3==0 then iterate; if j// 37==0 then iterate /" " " 3?; J ÷ by 7? / ~~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.#= jj; !.j= 1 /bump # of Ps; assign next P; P²; P# / end /j/; return</~~lang~~syntaxhighlight> {{out\|output\|text=  when using the default inputs:}} <pre> 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 </pre> =={{header\|Ring}}== <~~lang~~syntaxhighlight lang="ring"> load "stdlib.ring" Line 243 ⟶ 1,008: see nl + "Found " + row + " numbers in which all substrings are primes" + nl see "done..." + nl </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 253 ⟶ 1,018: </pre> =={{header\|~~Wren~~Rust}}== <syntaxhighlight lang="rust">use primes::is_prime; ~~{{libheader\|Wren-math}}~~ ~~<lang ecmascript>import "/math" for Int~~ fn counted_prime_test() { ~~var getDigits = Fn.new { \|n\|~~ ~~var~~let ~~digits~~mut number_of_prime_tests = []0; ~~while~~let (nmut >non_primes = vec![0); {0]; // start with 1 ~~digits.add(n%10)~~digit primes let mut results: Vec<i32> = [2, 3, 5, 7].to_vec(); ~~n = (n/10).floor~~ // 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 ~~return digits[-1..0]~~ 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(); } </syntaxhighlight>{{out}} <pre> 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. </pre> =={{header\|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 ≫ ≫ '<span style="color:blue">A085823</span>' STO {{out}} <pre> 3: { 2 3 5 7 23 37 53 73 373 } 2: { } 1: 10 </pre> =={{header\|Sidef}}== Generic solution for any base >= 2. <syntaxhighlight lang="ruby">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)}" }</syntaxhighlight> {{out}} <pre> 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] </pre> =={{header\|Wren}}== {{libheader\|Wren-math}} ===Using a limit=== <syntaxhighlight lang="wren">import "./math" for Int var primes = Int.primeSieve(499) var sprimes = [] for (p in primes) { var digits = ~~getDigits~~Int.~~call~~digits(p) var b1 = digits.all { \|d\| Int.isPrime(d) } if (b1) { Line 282 ⟶ 1,204: } System.print("Found %(sprimes.count) primes < 500 where all substrings are also primes, namely:") System.print(sprimes)</~~lang~~syntaxhighlight> {{out}} Line 288 ⟶ 1,210: Found 9 primes < 500 where all substrings are also primes, namely: [2, 3, 5, 7, 23, 37, 53, 73, 373] </pre> ===Advanced=== This follows the logic in the OEIS A085823 comments. <syntaxhighlight lang="wren">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)")</syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|XPL0}}== <syntaxhighlight lang="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, ^ )]; ]; ]</syntaxhighlight> {{out}} <pre> 2 3 5 7 23 37 53 73 373 </pre>