# Print/Output all positive numbers in which every multi-digit substring in its decimal representation is also prime.

Your task is to print or output all positive numbers in which every multi-digit substring in its decimal representation is also prime. If the number has at least 2 digits, this would imply that the number itself also needs to be prime.

# Example

• 6197 is in the sequence because every multi-digit substring in 6197 is prime, namely: 61, 19, 97, 619, 197, 6197 (itself).
• Note that 6 is not a prime but 6197 is still in the sequence because 6 is not a multi-digit substring of 6197.
• 8 is also in the sequence because every multi-digit substring in 8 is prime. There is no multi-digit substring in 8, so this is a case of vacuous truth.

# Specs

• Standard loopholes apply, except that you are allowed to hardcode the output or store information related to the output in your program.
• The numbers in the output can be in any order.
• The numbers in the output are allowed to have duplicates.
• You may use any separator, if you choose to print instead of output.
• You are allowed to prefix and/or postfix output if you choose to print instead of output.
• The separator and the prefix and the postfix may not contain any digits (U+0030 to U+0039).

# Full list (58 items)

1
2
3
4
5
6
7
8
9
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
113
131
137
173
179
197
311
313
317
373
379
419
431
479
613
617
619
673
719
797
971
1373
3137
3797
6131
6173
6197
9719


# Reference

As always, please feel free to address in the comments anything I should clarify.

• For reference, it's 200 bytes simply for the string of digits. – AdmBorkBork Aug 16 '16 at 15:05
• @Dopapp "standard loopholes apply" – Leaky Nun Aug 16 '16 at 15:09
• I will give +300 bounty to anyone except @Fatalize who submits the smallest answer to this challenge in Brachylog (wiki link) (TIO link) (chatroom). – Leaky Nun Aug 16 '16 at 16:17
• Poor @Fatalize. That's what you get for creating a language – Luis Mendo Aug 16 '16 at 16:31
• I have a 50 bytes answer :( – Fatalize Aug 17 '16 at 6:48

# 05AB1E, 15 13 bytes

Code:

4°GN§ŒD9›ÏpP–


Explanation:

  G            # For N in range 1,
4°             #   10000
N           # Push N
§          # Convert that to string
Œ         # Get all substrings
D9›Ï     # Keep all substrings that are greater than 9
p    # Check each of them if they are prime
P   # Product
–  # If 1, print N


Uses the CP-1252 encoding. Try it online! (might take a few seconds).

# Brachylog, 18 bytes

9719⟦₁{sᶠℕ₁₀ˢṗᵐ&}ˢ


Try it online!

So...am I ready for the "bounty"? :D

# Jelly, 17 bytes

DẆṖÐfḌÆP€Ạ
³²RÇÐf


My first Jelly answer! Saved 3 bytes thanks to @Leaky Nun!

Try it online

Explanation:

DẆṖÐfḌÆP€Ạ      The helper link, which checks if a given number satisfy the conditions.
DẆ              Convert the argument to a list of its digits and get all its substrings.
ṖÐf           Remove all lists of length 1.
ḌÆP€Ạ      Convert back each element to an integer and check if all of them are prime.

³²              Create a 100 and square it, which gives 10000.
R             Create a list from 1 to it.
ÇÐf          Filter out all the elements where the helper link gives false.

• Congratulations on your first Jelly answer! – Leaky Nun Aug 16 '16 at 17:05
• RÇÐf can be replaced with Ç€T. ṖÐfḌÆP€ can be replaced with ḌḟDÆP. – Dennis Aug 16 '16 at 19:56

# Java 8, 182 bytes

v->{for(int n=0;++n<1e4;)if(P(n)>0)System.out.println(n);}int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}int P(int n){return n>99?p(n)*p(n%100)*p(n%1000)*P(n/10):n<10?n:p(n);}


Port of gastropner's C (gcc) answer, so make sure to upvote his answer!

Try it online.

Explanation:

// Loop in range [1,10000), and print any primes corresponding to the challenge description
v->{for(int n=0;++n<1e4;)if(P(n)>0)System.out.println(n);}

// Checks if the given integer is a prime (return unchanged input if prime, 0 if not)
int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}

// Recursive method that checks if every part of length 2+ is a prime, or is below 10
int P(int n){return n>99?p(n)*p(n%100)*p(n%1000)*P(n/10):n<10?n:p(n);}


## PowerShell v2+, 107 104 bytes

1..10+(11..1e4|?{($x=11..($i=$_)|?{"$i"-match$_}).count-eq($x|?{'1'*$_-match'^(?!(..+)\1+$)..'}).count})


Warning: Kinda Slow

Loops from 11 to 1e4 (i.e., 10000) and pulls out numbers using the Where-Object selector (|?{...}). The clause is two components -- the first loops from 11 up to the current number and uses Where-Object to pull out those numbers that form a substring of the current number (via the -match regex operator). We store those substrings in $x. The second portion loops through $x and uses Where-Object to pull out all primes using the prime regex. We then take the .count of both and the check is actually whether those are -equal. For example, 971 will have $x = (71,97,971) and each of those are prime, so 3-eq3 is $TRUE and thus 971 will be selected.

That result is array-concatenated with a range 1..10. The resulting array is left on the pipeline and output is implicit, with a newline between elements by default.

# C (gcc), 144142140 136 bytes

-2 thanks to Kevin Cruijssen.

...And inspired by that, we can get another 2 bytes from that for loop.

Also shamelessly nicked the rather better prime checker from Kevin Cruijssen's answer for another -4.

p(n,i){for(i=2;i<n;)n=n%i++?n:0;i=n;}P(n){n=n>99?p(n)*p(n%100)*p(n%1000)*P(n/10):p(n)|n<10;}f(n){for(n=1e4;--n;)P(n)&&printf("%d\n",n);}


Try it online!

• ||n<10 can be |n<10 and for(n=1;n<1e4;n++) can be for(n=0;++n<1e4;) for -2 bytes. – Kevin Cruijssen Mar 29 '18 at 11:34
• @KevinCruijssen Cheers! – gastropner Mar 29 '18 at 14:26

# Ruby, 81 + 8 = 89 bytes

+8 bytes for -rprime.

puts (?1..?9*4).select{|m|(r=2..m.size).all?{|i|r.all?{|j|m[i-2,j].to_i.prime?}}}


See it on repl.it: https://repl.it/CniR/2

# Perl 6,  47 44  43 bytes

for 1..9719 {all(m:ex/..+/).Int.is-prime&&.say}
put grep {is-prime +all(m:ex/..+/):},1..9719
put grep {is-prime +all m:ex/..+/:},1..9719

## Explanation:

# print the values space separated, with trailing newline
put

# that match
grep -> $_ { # call the method ｢.is-prime｣ ( that is what ｢:｣ is for ) # (autothreaded) is-prime # convert following to numeric (autothreaded) + # a junction of all( # all substrings 2 characters or greater$_ ~~ m :exhaustive / . .+ /
)

# needed to indicate that ｢is-prime｣ is a method call
:

},

# in this Range
1..9719


## C#, 261249 247 bytes

Saved 12 bytes thanks to Leaky Nun

()=>{Action<int>w=System.Console.WriteLine;int i=0,n,j,k,p,m,b;for(;++i<10001;){n=(i+"").Length;if(n<2)w(i);else{b=1;for(j=1;++j<=n;)for(k=0;k+j<=n;){p=int.Parse((i+"").Substring(k++,j));if(p%2<1)b=0;for(m=3;m<p;m+=2)if(p%m<1)b=0;}if(b>0)w(i);}}};


This compiles to a Func<List<int>>.

The formatted version looks like:

() =>
{
Action<int> w = System.Console.WriteLine;

int i = 0, n, j, k, p, m, b;

for (; ++i < 10001;)
{
n = (i + "").Length;

if (n < 2)
w(i);

else
{
b = 1;
for (j = 1; ++j <= n; )
for (k = 0; k + j <= n; )
{
p = int.Parse((i + "").Substring(k++, j));

if (p % 2 < 1)
b = 0;

for (m = 3; m < p; m += 2)
if (p % m < 1)
b = 0;
}

if (b > 0)
w(i);
}
}
};

• Just print it directly without using a list – Leaky Nun Aug 16 '16 at 16:14
• Instead of false or true, use 0>1 and 0<1 – Leaky Nun Aug 16 '16 at 16:14
• You may refer to this for additional golfing tips. – Leaky Nun Aug 16 '16 at 16:15
• @LeakyNun Thanks for the tips, I usually like to get a kinda golfed version posted then move from there. – TheLethalCoder Aug 16 '16 at 16:15

# Swift 4, 144 bytes

let p={n in !(2..<n).contains{n%$0<1}} print((1...971).filter{$0<10||p($0)&&($0<100||p($0/10)&&p($0%100))}+[1373,3137,3797,6131,6173,6197,9719])


Try it online!

## Explanation

let p={n in !(2..<n).contains{n%$0<1}} // Helper function p, tests if a number is prime print((1...971).filter{ // Print every number n in the range 1 to 971$0<10                                 //  that is less than 10
||p($0)&& // or a prime and ($0<100                               //   is less than 100 or
||p($0/10)&&p($0%100))}              //   n/10 and n%100 are primes
+[1373,3137,3797,6131,6173,6197,9719]) // Print the four digit numbers


# JavaScript (Node.js), 130 bytes

if i can assume infinite stack i*i<=n&& can be removed and i*i>n turns to i>=n which reduces the code by 9 bytes and maybe convert main function to recursive : https://tio.run/##LYpBDoIwEEX33AMyAxVbXUmccgX2xkWDRYeQaSPqyrvXkrj5ef/lze7j1vHJ8bWTcPMpTQRMWjm6XJFs0/DZ@EM/ASunBmCsKtfG9/rIiJ0rIoEoJpNbKXPdx@1jx5akGEiytqdNYp2nNFr/wR@xHkD2Rn81dpLGIGtYfLuEO0yAmH4 (119 bytes)

_=>eval(for(a=[i=1];++i<1e4;)P(i)&&a.push(i))||a
p=(n,i=1)=>i*i<=n&&n%++i?p(n,i):n%i
P=n=>n>9?p(n)*p(n%100)*p(n%1e3)*P(n/10|0):n


Try it online!