Substring primes
Find all primes in which all substrings (in base ten) are also 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
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.
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)- 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
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- Output:
Screenshot from Atari 8-bit computer
2 3 5 7 23 37 53 73 373
BEGIN # find primes where all substrings of the digits are prime #
# find the primes of interest #
PR read "primes.incl.a68" PR
[]BOOL prime = PRIMESIEVE 500;
FOR p TO UPB prime DO
IF prime[ p ] THEN
INT d := 10;
BOOL is substring := TRUE;
WHILE is substring AND d <= UPB prime DO
INT n := p;
WHILE is substring AND n > 0 DO
is substring := prime[ n MOD d ];
n OVERAB 10
OD;
d *:= 10
OD;
IF is substring THEN print( ( " ", whole( p, 0 ) ) ) FI
FI
OD
END- Output:
2 3 5 7 23 37 53 73 373
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.
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.- Output:
2 3 5 7 23 37 53 73 373 Found 9 substring primes
# 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)
}
- Output:
2 3 5 7 23 37 53 73 373 SubString Primes 1-500: 9
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
- Output:
Igual que la entrada de FreeBASIC.
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()
- Output:
Igual que la entrada de 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
- Output:
Igual que la entrada de FreeBASIC.
#include <iostream>
#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;
}
- Output:
2 3 5 7 23 37 53 73 373
Advanced
#include <cstdint>
#include <iostream>
#include <vector>
template <typename T>
void print_vector(const std::vector<T>& vec) {
std::cout << "[";
for ( uint32_t i = 0; i < vec.size() - 1; ++i ) {
std::cout << vec[i] << ", ";
}
std::cout << vec.back() << "]" << std::endl;
}
bool is_prime(const uint32_t& number) {
if ( number % 2 == 0 ) {
return number == 2;
}
uint32_t k = 3;
while ( k * k <= number ) {
if ( number % k == 0 ) {
return false;
}
k += 2;
}
return true;
}
int main() {
// Begin with 1 digit primes
std::vector<uint32_t> primes = { 2, 3, 5, 7 };
std::vector<uint32_t> composites;
uint32_t test_count = 4; // Tests required to obtain the initial primes
// Search for 2-digit substring primes
std::vector<uint32_t> primes_copy(primes.begin(), primes.end());
for ( uint32_t prime : primes_copy ) {
// Additional digits must be 3 or 7 otherwise a composite substring would exist
for ( uint32_t digit : { 3, 7 } ) {
// If 'prime' and 'digit' are the same, 'number' would be divisible by 11
if ( prime != digit ) {
const uint32_t number = prime * 10 + digit;
if ( is_prime(number) ) {
primes.emplace_back(number);
} else {
composites.emplace_back(number);
}
test_count++;
}
}
}
// Search for 3-digit substring primes
for ( uint32_t prime : primes ) {
for ( uint32_t digit : { 3, 7 } ) {
// Only test two digit 'primes'
// If the last digit of 'prime' and 'digit' are the same, 'number' would be divisible by 11
if ( 10 < prime && prime < 100 && prime % 10 != digit ) {
const uint32_t number = prime * 10 + digit;
if ( is_prime(number) ) {
primes.emplace_back(number);
} else {
composites.emplace_back(number);
}
test_count++;
}
}
}
std::cout << "There are " << primes.size() << " primes where all substrings are also primes, namely: ";
print_vector(primes);
std::cout << "\nThe following numbers were tested for primality, but found to be composite: ";
print_vector(composites);
std::cout << "\nTotal number of primality tests: " << test_count << std::endl;
}
- 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 tested for primality, but found to be composite: [27, 57, 237, 537, 737] Total number of primality tests: 14
Note that there is no point in testing any larger numbers because 373 can only produce the numbers 3733 and 3737. These numbers have composite substrings 33 and 737 respectively.
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;
- Output:
2 3 5 7 23 37 53 73 373 Elapsed Time: 8.708 ms.
fastfunc isprim n .
i = 2
while i <= sqrt n
if n mod i = 0 : return 0
i += 1
.
return 1
.
digs[] = [ 2 3 5 7 ]
#
for p in digs[] : write p & " "
for d1 in digs[] : for d2 in digs[]
h = d1 * 10 + d2
if isprim h = 1 : write h & " "
.
for d1 in digs[] : for d2 in digs[] : for d3 in digs[]
h = d1 * 100 + d2 * 10 + d3
if h >= 500 : break 1
if isprim h = 1 and isprim (h div 10) = 1 and isprim (h mod 100) = 1
write h & " "
.
.
print ""- Output:
2 3 5 7 23 37 53 73 373
For fun, a translation of FreeBASIC.
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 .
- Output:
V{ 2 3 5 7 23 37 53 73 373 }
Since this is limited to one, two, or three-digit numbers I will be a bit cheeky.
#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
- Output:
2 3 5 7 23 37 53 73 373
Using a limit
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)
}
- Output:
Found 9 primes < 500 where all substrings are also primes, namely: [2 3 5 7 23 37 53 73 373]
Advanced
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)
}
- 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
import module java.base;
public final class SubstringPrimes {
public static void main() {
Predicate<Integer> isPrime = n ->
IntStream.rangeClosed(2, (int) Math.sqrt(n)).noneMatch( i -> n % i == 0 );
// Begin with 1 digit primes
List<Integer> primes = Stream.of( 2, 3, 5, 7 ).collect(Collectors.toList());
List<Integer> composites = new ArrayList<Integer>();
int testCount = 4; // Tests required to obtain the initial primes
// Search for 2-digit substring primes
for ( int prime : new ArrayList<Integer>(primes) ) {
// Additional digits must be 3 or 7 otherwise a composite substring would exist
for ( int digit : List.of( 3, 7 ) ) {
// If 'prime' and 'digit' are the same, 'number' would be divisible by 11
if ( prime != digit ) {
final int number = prime * 10 + digit;
if ( isPrime.test(number) ) {
primes.addLast(number);
} else {
composites.addLast(number);
}
testCount += 1;
}
}
}
// Search for 3-digit substring primes
for ( int prime : new ArrayList<Integer>(primes) ) {
for ( int digit : List.of( 3, 7 ) ) {
// Only test two digit 'primes'
// If the last digit of 'prime' and 'digit' are the same, 'number' would be divisible by 11
if ( 10 < prime && prime < 100 && prime % 10 != digit ) {
final int number = prime * 10 + digit;
if ( isPrime.test(number) ) {
primes.addLast(number);
} else {
composites.add(number);
}
testCount += 1;
}
}
}
IO.println("There are %d primes where all substrings are also primes, namely: %s"
.formatted(primes.size(), primes));
IO.println("\nThe following numbers were tested for primality, but found to be composite: " + composites);
IO.println("\nTotal number of primality tests: " + testCount);
}
}
- 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 tested for primality but found to be composite: [27, 57, 237, 537, 737] Total number of primality tests: 14
Note that there is no point in testing any larger numbers because 373 can only produce the numbers 3733 and 3737. These numbers have composite substrings 33 and 737 respectively.
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ős-primes#jq for a suitable implementation of `is_prime`.
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 )- Output:
Verifying that the following are the only substring primes: [2,3,5,7,23,37,53,73,373] ... done
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))
- Output:
[2, 3, 5, 7, 23, 37, 53, 73, 373]
Advanced task
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.
- 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]
Select[Range[500], PrimeQ[#] && AllTrue[Subsequences[IntegerDigits[#], {1, \[Infinity]}], FromDigits /* PrimeQ] &]
- Output:
{2, 3, 5, 7, 23, 37, 53, 73, 373}
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.
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
- Output:
List of substring primes: 2 3 5 7 23 37 53 73 373 Number of primality tests: 11
#!/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;
- Output:
2 3 5 7 23 37 53 73 373
Or
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Substring_primes
use warnings;
use ntheory qw( is_prime primes );
my $pattern = join '|', grep !is_prime($_), 1 .. 500;
my @primes = grep !/$pattern/, @{ primes( 500 ) };
print "@primes\n";
- Output:
2 3 5 7 23 37 53 73 373
This tests a total of just 15 numbers for primality.
with javascript_semantics
--sequence tested = {}
--function a085823(integer p=0)
-- sequence res={}
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)
{res,tested} = a085823(deep_copy(res)&t,deep_copy(tested),t) -- [1]
-- res &= t
-- res &= a085823(t)
else
tested &= t
end if
end if
end for
return {res,tested}
-- return res
end function
sequence {res,tested} = a085823() -- sort() if you prefer...
--sequence res = 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})
[1]It is possible that the compiler could be improved to avoid the need for those deep_copy().
The other seven commented out lines show a different way to avoid any use of deep_copy().
- 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}
Checking via substrings
% 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).- Output:
[2,3,5,7,23,37,53,73,373]
Checking via predicate
Here we must use cut (!) 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.
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))).- Output:
[2,3,5,7,23,37,53,73,373]
Using a limit
local int = require "int"
local fmt = require "fmt"
local primes = int.primes(499)
local sprimes = {}
for primes as p do
local digits = int.digits(p)
local b1 = digits:checkall(|d| -> int.isprime(d))
if b1 then
if #digits < 3 then
sprimes:insert(p)
else
local b2 = int.isprime(digits[1] * 10 + digits[2])
local b3 = int.isprime(digits[2] * 10 + digits[3])
if b2 and b3 then sprimes:insert(p) end
end
end
end
print($"Found {#sprimes} primes < 500 where all substrings are also primes, namely:")
fmt.lprint(sprimes)
- Output:
Found 9 primes < 500 where all substrings are also primes, namely:
{2, 3, 5, 7, 23, 37, 53, 73, 373}
Advanced
local int = require "int"
local fmt = require "fmt"
local primes = int.primes(499)
local sprimes = {}
for primes as p do
local digits = int.digits(p)
local b1 = digits:checkall(|d| -> int.isprime(d))
if b1 then
if #digits < 3 then
sprimes:insert(p)
else
local b2 = int.isprime(digits[1] * 10 + digits[2])
local b3 = int.isprime(digits[2] * 10 + digits[3])
if b2 and b3 then sprimes:insert(p) end
end
end
end
print($"Found {#sprimes} primes < 500 where all substrings are also primes, namely:")
fmt.lprint(sprimes)
- 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
import math
def is_prime(n: int):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
def main():
primes = []
for i in range(2, 500):
if i < 10:
if is_prime(i):
primes.append(i)
else:
prime_check = True
num_str = str(i)
for ii in range(len(num_str)):
for j in range(ii+1, len(num_str)+1):
if not is_prime(int(num_str[ii:j])):
prime_check = False
break
if not prime_check:
break
else:
primes.append(i)
print("Found %d primes < 500 where all substrings are also primes, namely:" % len(primes))
print(primes)
if __name__ == '__main__':
main()
- Output:
Found 9 primes < 500 where all substrings are also primes, namely: [2, 3, 5, 7, 23, 37, 53, 73, 373]
This solution doesn't test whether the last two digits of each number are the same, so tests one more number than is strictly necessary (but does manage to avoid testing 3737 as it contains 737 which is known to be composite).
library(gmp)
#Start with the one-digit primes and an empty vector of composites
primes <- c(2, 3, 5, 7)
comps <- c()
repeat {
np <- length(primes)
#Append 3 and 7 to existing primes to get new possible primes
#(No digit except the first can be 2 or 5)
poss_primes <- outer(primes, c(3, 7), paste0) |> `dim<-`(NULL) |> as.numeric()
#Check no substrings of possible primes are composite
for (n in comps) poss_primes <- setdiff(poss_primes, grepv(n, poss_primes))
#Update lists of which numbers found are prime and which are not
primes <- union(primes, Filter(isprime, poss_primes))
comps <- union(comps, setdiff(poss_primes, primes))
#If no new primes are added, we are done
if (length(primes) == np) break
}
cat(
"These are all substring primes:", sort(primes),
"\nThese numbers were tested but found to be composite:", sort(comps)
)
- Output:
These are all substring primes: 2 3 5 7 23 37 53 73 373 These numbers were tested but found to be composite: 27 33 57 77 237 537 737
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 }
}
- Output:
(2 3 5 7 23 37 53 73 373)
Stretch Goal
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;
- Output:
(2 3 5 7 23 37 53 73 373) prime-tests => 11 non-primes => [27 57 237 537 737 3737]
Modules: How to use
Modules: Source code
Filters to avoid prime tests: digits must be 2357, primes < 10 always apply, no digits 2 or 5 after the first, two adjacent digits must be different.
-- 24 Aug 2025
include Setting
call Time('r')
say 'SUBSTRING PRIMES'
say version
say
call Task
call Stretch
say Format(Time('e'),,3) 'seconds'
exit
Task:
procedure expose test.
say 'Substring primes below' 500'...'
n = 0; test.0 = 0; test.1 = ''
do i = 1 to 500
if Substring(i) then do
n = n+1
call Charout ,i' '
end
end
say
say n 'found'
say
return
Substring:
procedure expose test.
arg xx
if Verify(xx,014689,'m') > 0 then
return 0
if xx < 10 then
return 1
if Verify(Substr(xx,2),25,'m') > 0 then
return 0
l = Length(xx)
do i = 1 to l-1
if Substr(xx,i,1) = Substr(xx,i+1,1) then
return 0
end
do i = 2 to l-1
do j = i+1 to l
a = Substr(xx,i,j-1)
test.0 = test.0+1
if \ Prime(a) then do
test.1 = test.1 a
return 0
end
end
end
test.0 = test.0+1
if Prime(xx) then
return 1
else do
test.1 = test.1 xx
return 0
end
Stretch:
procedure expose test.
say 'Tested for primality, but found composite...'
say strip(test.1)
say 'In total' test.0 'primality tests performed'
say
return
include Math
- Output:
SUBSTRING PRIMES REXX-Regina_3.9.7(MT) 5.00 18 Mar 2025 Substring primes below 500... 2 3 5 7 23 37 53 73 373 9 found Tested for primality, but found composite... 27 57 237 273 In total 12 primality tests performed 0.001 seconds
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- 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...
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();
}
- Output:
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.
≪ { 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
≫ ≫ 'A085823' STO
- Output:
3: { 2 3 5 7 23 37 53 73 373 }
2: { }
1: 10
Generic solution for any base >= 2.
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)}"
}
- Output:
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]
Using a limit
import "./math" for Int
var primes = Int.primeSieve(499)
var sprimes = []
for (p in primes) {
var digits = Int.digits(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)
- 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.
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)")
- 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
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, ^ )];
];
]- Output:
2 3 5 7 23 37 53 73 373