Substring primes: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (27 intermediate revisions by 18 users not shown) | |||
Line 11:
Solve by testing at most 15 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}}
<syntaxhighlight lang="algol68">BEGIN # find primes where all substrings of the digits are prime #
# find the primes of interest #
PR read "primes.incl.a68" PR
[]BOOL prime =
FOR p TO UPB prime DO
IF prime[ p ] THEN
INT d := 10;
BOOL is substring := TRUE;
WHILE is substring AND d <=
INT n := p;
WHILE is substring AND n > 0 DO
n OVERAB 10
OD;
Line 45 ⟶ 135:
FI
OD
END</
{{out}}
<pre>
Line 53 ⟶ 143:
=={{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.
<
% sets p( 1 :: n ) to a sieve of primes up to n %
procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
Line 102 ⟶ 192:
write( i_w := 1, s_w := 0, "Found ", sCount, " substring primes" )
end
end.</
{{out}}
<pre>
Line 109 ⟶ 199:
</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SUBSTRING_PRIMES.AWK
# converted from FreeBASIC
Line 146 ⟶ 236:
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 152 ⟶ 242:
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++}}==
<
#include <vector>
Line 198 ⟶ 401:
}
return 0;
}</
{{out}}
Line 211 ⟶ 414:
73
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.
<
function is_ssp(n as uinteger) as boolean
Line 232 ⟶ 505:
if is_ssp(i) then print i;" ";
next i
print</
{{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 := 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)
}</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}}==
<
const pmask = primesmask(1, 1000)
Line 250 ⟶ 678:
println(filter(isA085823, 1:1000))
</
<pre>
[2, 3, 5, 7, 23, 37, 53, 73, 373]
</pre>
=== Advanced task ===
<
const nt, nons = [0], Int[]
Line 284 ⟶ 712:
# Because 237, 537, and 737 are already excluded, we cannot generate any larger candidates from 373.
</
<pre>
Results: [2, 3, 5, 7, 23, 37, 53, 73, 373].
Line 290 ⟶ 718:
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}}==
<
use strict; # https://rosettacode.org/wiki/Substring_primes
Line 310 ⟶ 793:
}
}
printf " %d" x %prime . "\n", sort {$a <=> $b} keys %prime;</
{{out}}
2 3 5 7 23 37 53 73 373
Line 317 ⟶ 800:
=={{header|Phix}}==
This tests a total of just 15 numbers for primality.
<!--<
<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;">4</span> <span style="color: #008080;">do</span>
Line 324 ⟶ 811:
<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: #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 331 ⟶ 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...
--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>
<!--</
<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>
Line 342 ⟶ 836:
6 innocent bystanders falsly accused of being prime (15 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"
say gather while @p {
Line 350 ⟶ 887:
@p = ( @p X~ <3 7> ).grep: { .is-prime and .substr(*-2,2).is-prime }
}</
{{out}}
<pre>
(2 3 5 7 23 37 53 73 373)</pre>
===Stretch Goal===
<syntaxhighlight lang="raku"
my @non-primes;
sub spy-prime ($n) {
Line 372 ⟶ 909:
@p = ( @p X~ <3 7> ).grep: { !.ends-with(33|77) and .&spy-prime };
}
.say for :$prime-tests, :@non-primes;</
{{out}}
<pre>
Line 380 ⟶ 917:
=={{header|REXX}}==
<
parse arg
if
if cols=='' | cols=="," then cols= 10 /* " " " " " " */
call genP /*build array of semaphores for primes.*/
w=
say ' index │'center(
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 #;
if verify(
if verify(
L= length(
do k=1 for L-1 /*test for primality for all substrings*/
do m=k+1 to L; y= substr(
if \!.y then iterate j /*does substring of
end /*m*/
end /*k*/
$= $ 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(
say
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
parse var j '' -1 _;
if j//3==0 then
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</
{{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}}==
<
load "stdlib.ring"
Line 464 ⟶ 1,008:
see nl + "Found " + row + " numbers in which all substrings are primes" + nl
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
Line 474 ⟶ 1,018:
</pre>
=={{header|
<syntaxhighlight lang="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();
}
</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 =
var b1 = digits.all { |d| Int.isPrime(d) }
if (b1) {
Line 505 ⟶ 1,204:
}
System.print("Found %(sprimes.count) primes < 500 where all substrings are also primes, namely:")
System.print(sprimes)</
{{out}}
Line 515 ⟶ 1,214:
===Advanced===
This follows the logic in the OEIS A085823 comments.
<
var results = [2, 3, 5, 7] // number must begin with a prime digit
Line 539 ⟶ 1,238:
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)")</
{{out}}
Line 550 ⟶ 1,249:
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>
| |||