Substring primes
Find all primes in which all substrings (in base ten) are also primes.
- Task
- Advanced
Solve by testing at most 15 numbers for primality. Show a list of all numbers tested that were not prime.
ALGOL 68
<lang algol68>BEGIN # find primes where all substrings of the digits are prime #
# reurns a sieve of primes up to n #
PROC sieve = ( INT n )[]BOOL:
BEGIN
[ 1 : n ]BOOL p;
p[ 1 ] := FALSE; p[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO n DO p[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO n DO p[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO
IF p[ i ] THEN FOR s FROM i * i BY i + i TO n DO p[ s ] := FALSE OD FI
OD;
p
END # prime list # ;
# find the primes of interest #
INT max number = 500;
[]BOOL prime = sieve( max number );
FOR p TO UPB prime DO
IF prime[ p ] THEN
INT d := 10;
BOOL is substring := TRUE;
WHILE is substring AND d <= max number DO
INT n := p;
WHILE is substring AND n > 0 DO
INT sub digits = n MOD d;
is substring := IF sub digits = 0 THEN FALSE ELSE prime[ sub digits ] FI;
n OVERAB 10
OD;
d *:= 10
OD;
IF is substring THEN print( ( " ", whole( p, 0 ) ) ) FI
FI
OD
END</lang>
- Output:
2 3 5 7 23 37 53 73 373
ALGOL W
starts with a hardcoded list of 1 digit primes ( 2, 3, 5, 7 ) and constructs the remaining members of the sequence (in order) using the observations that the final digit must be prime and can't be 2 or 5 or the number wouldn't be prime. Additionally, the final digit pair cannot be 33 or 77 as these are divisible by 11. <lang algolw>begin % find primes where every substring of the digits is also priome %
% sets p( 1 :: n ) to a sieve of primes up to n %
procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
begin
p( 1 ) := false; p( 2 ) := true;
for i := 3 step 2 until n do p( i ) := true;
for i := 4 step 2 until n do p( i ) := false;
for i := 3 step 2 until truncate( sqrt( n ) ) do begin
integer ii; ii := i + i;
if p( i ) then for s := i * i step ii until n do p( s ) := false
end for_i ;
end Eratosthenes ;
% it can be shown that all the required primes are under 1000, however we will %
% not assume this, so we will allow for 4 digit numbers %
integer MAX_NUMBER, MAX_SUBSTRING;
MAX_NUMBER := 10000;
MAX_SUBSTRING := 100; % assume there will be at most 100 such primes %
begin
logical array prime( 1 :: MAX_NUMBER );
integer array sPrime( 1 :: MAX_SUBSTRING );
integer tCount, sCount, sPos;
% adds a substring prime to the list %
procedure addPrime ( integer value p ) ;
begin
sCount := sCount + 1;
sPrime( sCount ) := p;
writeon( i_w := 1, s_w := 0, " ", p )
end addPrime ;
% sieve the primes to MAX_NUMBER %
Eratosthenes( prime, MAX_NUMBER );
% clearly, the 1 digit primes are all substring primes %
sCount := 0;
for i := 1 until MAX_SUBSTRING do sPrime( i ) := 0;
for i := 2, 3, 5, 7 do addPrime( i );
% the subsequent primes can only have 3 or 7 as a final digit as they must end %
% with a prime digit and 2 and 5 would mean the number was divisible by 2 or 5 %
% as all substrings on the prime must also be prime, 33 and 77 are not possible %
% final digit pairs %
sPos := 1;
while sPrime( sPos ) not = 0 do begin
integer n3, n7;
n3 := ( sPrime( sPos ) * 10 ) + 3;
n7 := ( sPrime( sPos ) * 10 ) + 7;
if sPrime( sPos ) rem 10 not = 3 and prime( n3 ) then addPrime( n3 );
if sPrime( sPos ) rem 10 not = 7 and prime( n7 ) then addPrime( n7 );
sPos := sPos + 1
end while_sPrime_sPos_ne_0 ;
write( i_w := 1, s_w := 0, "Found ", sCount, " substring primes" )
end
end.</lang>
- Output:
2 3 5 7 23 37 53 73 373 Found 9 substring primes
C++
<lang cpp>#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;
}</lang>
- Output:
2 3 5 7 23 37 53 73 373
FreeBASIC
Since this is limited to one, two, or three-digit numbers I will be a bit cheeky. <lang freebasic>#include "isprime.bas"
function is_ssp(n as uinteger) as boolean
if not isprime(n) then return false if n < 10 then return true if not isprime(n mod 100) then return false if not isprime(n mod 10) then return false if not isprime(n\10) then return false if n < 100 then return true if not isprime(n\100) then return false if not isprime( (n mod 100)\10 ) then return false return true
end function
for i as uinteger = 1 to 500
if is_ssp(i) then print i;" ";
next i print</lang>
{out}}
2 3 5 7 23 37 53 73 373
Julia
<lang julia>using Primes
const pmask = primesmask(1, 1000)
function isA085823(n, base = 10, sieve = pmask)
dig = digits(n; base=base)
for i in 1:length(dig), j in i:length(dig)
k = evalpoly(base, dig[i:j])
(k == 0 || !sieve[k]) && return false
end
return true
end
println(filter(isA085823, 1:1000))
</lang>
- Output:
[2, 3, 5, 7, 23, 37, 53, 73, 373]
Phix
This tests a total of just 15 numbers for primality.
function a085823(sequence res={}, tested={}, integer p=0) for i=(p!=0)+1 to 4 do integer t = get_prime(i) if t!=remainder(p,10) and (p=0 or t!=5) then t += p*10 if is_prime(t) then {res,tested} = a085823(res&t,tested,t) else tested &= t end if end if end for return {res,tested} end function sequence {res,tested} = a085823() -- sort() if you prefer... printf(1,"There are %d such A085823 primes: %V\n",{length(res),res}) printf(1,"%d innocent bystanders falsly accused of being prime (%d tests in total): %V\n", {length(tested),length(tested)+length(res),tested})
- Output:
There are 9 such A085823 primes: {2,23,3,37,373,5,53,7,73}
6 innocent bystanders falsly accused of being prime (15 tests in total): {237,27,3737,537,57,737}
Raku
<lang perl6>my @p = (^10).grep: *.is-prime;
say gather while @p {
.take for @p;
@p = ( @p X~ <3 7> ).grep: { .is-prime and .substr(*-2,2).is-prime }
}</lang>
- Output:
(2 3 5 7 23 37 53 73 373)
REXX
<lang rexx>/*REXX program finds/shows decimal primes where all substrings are also prime, N < 500.*/ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 500 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 7 /*width of a number in any column. */
@sprs= ' primes (base ten) where all substrings are also primes < ' hi
say ' index │'center(@sprs, 1 + cols*(w+1) ) /*display the title of the output. */ say '───────┼'center("" , 1 + cols*(w+1), '─') /* " " separator " " " */ $= /*a list of substring primes (so far). */
do j=1 for #; x= @.j; x2= substr(x, 2) /*search for primes that fit criteria. */
if verify(x, 014689, 'M')>0 then iterate /*does X prime have any of these digs?*/
if verify(x2, 25 , 'M')>0 then iterate /* " X2 part " " " " " */
L= length(x) /*obtain the length of the X prime.*/
do k=1 for L-1 /*test for primality for all substrings*/
do m=k+1 to L; y= substr(x, k, m-1) /*extract a substring from the X prime.*/
if \!.y then iterate j /*does substring of X not prime? Skip.*/
end /*m*/
end /*k*/
$= $ right(x, w) /*add the X prime to the $ list. */
end /*j*/
if $\== then say center(1,7)"│" substr($, 2) /*display the list of substring primes.*/ say; say 'Found ' words($) @sprs exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: !.= 0; ptests= 0 /*placeholders for primes (semaphores).*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */
#=5; s.#= @.# **2 /*number of primes so far; prime². */
/* [↓] generate more primes ≤ high.*/
do j=@.#+2 by 2 to hi /*find odd primes from here on. */
parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/
if j// 3==0 then iterate /*" " " 3? */
if j// 7==0 then iterate /*" " " 7? */
/* [↑] the above 3 lines saves time.*/
do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */
end /*j*/; return</lang>
- output when using the default inputs:
index │ primes (base ten) where all substrings are also primes < 500 ───────┼───────────────────────────────────────────────────────────────────────────────── 1 │ 2 3 5 7 23 37 53 73 373 Found 9 primes (base ten) where all substrings are also primes < 500
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl see "Numbers in which all substrings are primes:" + nl
row = 0 limit1 = 500
for n = 1 to limit1
flag = 1
strn = string(n)
for m = 1 to len(strn)
for p = 1 to len(strn)
temp = substr(strn,m,p)
if temp != ""
if isprime(number(temp))
flag = 1
else
flag = 0
exit 2
ok
ok
next
next
if flag = 1
see "" + n + " "
ok
next
see nl + "Found " + row + " numbers in which all substrings are primes" + nl see "done..." + nl </lang>
- Output:
working... Numbers in which all substrings are primes: 2 3 5 7 23 37 53 73 373 Found 9 numbers in which all substrings are primes done...
Wren
<lang ecmascript>import "/math" for Int
var getDigits = Fn.new { |n|
var digits = []
while (n > 0) {
digits.add(n%10)
n = (n/10).floor
}
return digits[-1..0]
}
var primes = Int.primeSieve(499) var sprimes = [] for (p in primes) {
var digits = getDigits.call(p)
var b1 = digits.all { |d| Int.isPrime(d) }
if (b1) {
if (digits.count < 3) {
sprimes.add(p)
} else {
var b2 = Int.isPrime(digits[0] * 10 + digits[1])
var b3 = Int.isPrime(digits[1] * 10 + digits[2])
if (b2 && b3) sprimes.add(p)
}
}
} System.print("Found %(sprimes.count) primes < 500 where all substrings are also primes, namely:") System.print(sprimes)</lang>
- Output:
Found 9 primes < 500 where all substrings are also primes, namely: [2, 3, 5, 7, 23, 37, 53, 73, 373]