11
\$\begingroup\$

Given a large number (in base 10), such as 1234567891011121314151617, find prime "subnumbers" in it.
A prime "subnumber" is a consecutive sequence of digits (taken from the input), which represents a prime number (in base 10).

  • Input: A number (either a string, a file, or whatever you like).
  • Output: All prime subnumbers separated somehow (either in a list, a file, comma-separated strings...) If the result is empty, you can take any convention you like (hardcoded string, empty string, gibberish, but program should not crash.
  • Example
    1234 -> 2, 3, 23
    6542 -> 5, 2
    14 -> [.. empty output]

This is code-golf. The shortest program wins!
[edit] : additional rule, program must be explained! Not everybody is fluent in Jelly :)

\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Luis felipe De jesus Munoz Aug 22 '18 at 12:04
  • \$\begingroup\$ Extremely related. \$\endgroup\$ – user202729 Aug 22 '18 at 12:04
  • 1
    \$\begingroup\$ not specified. Do whatever you like. \$\endgroup\$ – Regis Portalez Aug 22 '18 at 12:47
  • 1
    \$\begingroup\$ Tip: That's too soon to be accepting an answer; it can discourage others from posting solutions. \$\endgroup\$ – Shaggy Aug 22 '18 at 17:19
  • 2
    \$\begingroup\$ @RegisPortalez welcome, and nice challenge! I've found that the "accept" feature isn't used all that much anymore on PPCG the way it is on the other sites in the network. We tend to value nice answers in any language. \$\endgroup\$ – ngm Aug 22 '18 at 18:02

16 Answers 16

6
\$\begingroup\$

05AB1E (legacy), 3 bytes

Œʒp

Try it online!

Substrings of the input that are prime.

\$\endgroup\$
  • \$\begingroup\$ That will be hard to make shorter :) \$\endgroup\$ – Regis Portalez Aug 22 '18 at 12:21
  • \$\begingroup\$ Right language for this task \$\endgroup\$ – Jonathan Allan Aug 22 '18 at 12:34
  • 5
    \$\begingroup\$ @mob That depends on the encoding. In the 05AB1E encoding, this answer is 3 bytes long. \$\endgroup\$ – Dennis Aug 22 '18 at 13:59
  • 2
    \$\begingroup\$ According to this, 34567 = 13*2659 is prime, seems wrong : tio.run/##yy9OTMpM/f//6KRTkwr@/zc2MTUzBwA \$\endgroup\$ – frosqh Aug 22 '18 at 15:13
  • 2
    \$\begingroup\$ @frosqh It's actually a bug of the p (prime) function in the new 05AB1E release: tio.run/##yy9OTMpM/f//6KRTkwr@/zc2MTUzBwA It's already been fixed in the repository but hasn't been pushed on TIO. I've switched my answer to the legacy version in the meantime. \$\endgroup\$ – Kaldo Aug 22 '18 at 15:22
6
\$\begingroup\$

Perl 6, 28 bytes

{grep &is-prime,+«m:ex/.+/}

Try it online!

The :ex ("exhaustive") flag to the match operator m makes it return every possible match of .+ (ie, every substring of one or more characters), even overlapping ones. The hyperoperator turns that list of Match objects into numbers, which are then filtered for primeness by grep &is-prime.

\$\endgroup\$
  • \$\begingroup\$ Here I was going to go with {+«m:ex/(.+)<?{$0.is-prime}>/} \$\endgroup\$ – Brad Gilbert b2gills Aug 22 '18 at 19:27
  • \$\begingroup\$ @BradGilbertb2gills I tried that too! I'm a little disappointed it turned out to be longer. \$\endgroup\$ – Sean Aug 22 '18 at 19:57
  • \$\begingroup\$ Thanks for explaining - always helpful to Perl 4 dinosaurs like me! \$\endgroup\$ – Toby Speight Aug 23 '18 at 10:34
5
\$\begingroup\$

Brachylog, 4 bytes

-1 byte thanks to Kroppeb.

sᶠṗˢ

Try it online!

ind all substrings, ˢelect the rimes

\$\endgroup\$
5
\$\begingroup\$

Python 2, 66 65 bytes

P=k=1
n=input()
while~n+k:
 if`k`in`n`>0<P%k:print k
 P*=k*k;k+=1

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Should be while k<=n or, to cost 0 bytes, while~n+k \$\endgroup\$ – Jonathan Allan Aug 22 '18 at 17:55
  • \$\begingroup\$ @JonathanAllan thank you. At first I thought the number itself should be excluded from the output, but it seems like this isn't the case. \$\endgroup\$ – ovs Aug 22 '18 at 18:03
  • \$\begingroup\$ @JonathanAllan Can you explain please the code from the while statement? I haven't seen this type of codes before. Also haven't seen use of `` , what it does? \$\endgroup\$ – tarit goswami Aug 23 '18 at 13:57
  • 1
    \$\begingroup\$ @taritgoswami while stmt: will run as long as stmt has a value that is considered truthy by python. The only falsy integer in Python is 0. Therefore the code will run as ~n+k != 0. ~ is the bitwise complement operator, and ~n is equivalent to -n - 1. ~n + k != 0 <=> -n - 1 + k != 0 <=> k != n + 1. As we are incrementing k by 1 in every operation, k != n + 1 is in this case equivalent to k <= n. \$\endgroup\$ – ovs Aug 23 '18 at 14:05
  • 1
    \$\begingroup\$ @taritgoswami And `n` is the same as repr(n) in Python 2. (does not work in Python 3). \$\endgroup\$ – ovs Aug 23 '18 at 14:06
3
\$\begingroup\$

Japt, 13 10 bytes

Thanks @Shaggy -3 bytes

ò fj f@søX

ò fj f@søX              Full program
                        implicity input
ò                       inclusive range [this - 1]
  fj                    filter primes and
     f@søX              values contained in input

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 10 bytes \$\endgroup\$ – Shaggy Aug 22 '18 at 12:23
3
\$\begingroup\$

Jelly,  5  4 bytes

-1 thanks to Kevin Cruijssen ( is an alias for ÆP)

ẆḌẒƇ

A monadic Link accepting a list of digits* which yields a list of prime integers.

* going by "either a string, a file, or whatever you like" - to take an integer, prefix the code with a D

Try it online!

How?

ẆḌẒƇ - Link: list of integers (digits)   e.g. [1,2,3,4]
Ẇ    - non-empty contiguous substrings        [[1],[2],[3],[4],[1,2],[2,3],[3,4],[1,2,3],[2,3,4],[1,2,3,4]]
 Ḍ   - convert to decimal (vectorises)        [1,2,3,4,12,23,34,123,234,1234]
   Ƈ - filter keep if:
  Ẓ  -   is prime?                            [2,3,23]
\$\endgroup\$
  • \$\begingroup\$ ÆP can be if I'm not mistaken? \$\endgroup\$ – Kevin Cruijssen Aug 22 '18 at 12:55
  • \$\begingroup\$ Ah yes that is one of the new aliases - thanks! \$\endgroup\$ – Jonathan Allan Aug 22 '18 at 12:58
2
\$\begingroup\$

Java 8, 148 147 bytes

n->{for(int l=n.length(),i=l,j;i-->0;)for(j=l;j>i;){long k=2,x=new Long(n.substring(i,j--));for(;k<x;x=x%k++<1?0:x);if(x>1)System.out.println(x);}}

Try it online.

Explanation:

n->{                     // Method with String parameter and no return-type
  for(int l=n.length(),  //  Length of the input-String
          i=l,j;         //  Temp-integers
      i-->0;)            //  Loop `i` in the range [length, 0)
    for(j=l;j>i;){       //   Inner loop `j` in the range [length, 0)
      for(long k=2,      //    Set `k` to 2
               x=new Long(n.substring(i,j--)
                         //    Take the substring [`i`, `j`) from the input,
            );           //    convert it to a long, and set it as `x`
          k<x;           //    Inner loop as long as `k` is still smaller than `x`
        x=x%k++<1?       //     If `x` is divisible by `k`:
           0             //      Set `x` to 0
          :              //     Else:
           x);           //      Leave `x` unchanged
      if(x>1)            //    If `x` is now larger than 1 (a.k.a. If `x` is a prime):
        System.out.println(x);}}
                         //     Print `x` with a trailing newline to STDOUT
\$\endgroup\$
2
\$\begingroup\$

MATL, 9 bytes

&XfXUtZp)

Try it online!

Explanation

&Xf   % Implicit input: string. Push cell array of non-empty substrings
XU    % Convert to number. Vectorizes
t     % Duplicate
Zp    % Isprime. Vectorizes.
)     % Index. Keeps substrings indicated by the previous result. Implicit display
\$\endgroup\$
2
\$\begingroup\$

Bash + GNU Core Utils: 80 77 Bytes

for i in $(seq `tee a|wc -c`)
{
grep -oE .{$i}<a|factor|grep -oP ': \K\d+$'
}

This cannot be the shortest, but I am having trouble coming up with anything better. Help wanted!

By sticking to only POSIX, I got 82:

for i in $(seq `tee a|wc -c`)
{
grep -oE .{$i}<a|factor|awk -F\  'NF<3{print$2}'
}
\$\endgroup\$
  • \$\begingroup\$ Could Bash string slicing help? It's a shame brace ranges are expanded before parameters... \$\endgroup\$ – Toby Speight Aug 23 '18 at 10:33
  • \$\begingroup\$ @TobySpeight that would require two loops (one for the start, one for the end), not to mention you can't use variables inside of a slicing substitution. Zsh allows it, though! The main route to shortness in my mind is to use Awk to generate all the substrings. \$\endgroup\$ – markasoftware Aug 23 '18 at 18:49
2
\$\begingroup\$

R, 60 bytes

function(v)Filter(function(i)grepl(i,v)&sum(!i%%1:i)==2,1:v)

Try it online!

Not really efficient, inspired by @ovs python 2 answer

\$\endgroup\$
  • 1
    \$\begingroup\$ Awesome! funprog rules! \$\endgroup\$ – JayCe Aug 27 '18 at 19:10
1
\$\begingroup\$

Python 2, 115 114 bytes

f=lambda s:s and[n for n in[int(s[j:])for j in range(len(s))]if n>1and all(n%i for i in range(2,n))]+f(s[:-1])or[]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ if~-n*all(n%i for i in range(2,n)) saves 4. \$\endgroup\$ – Mr. Xcoder Aug 22 '18 at 14:49
0
\$\begingroup\$

Husk, 5 bytes

foṗiQ

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Clean, 108 bytes

import StdEnv,Data.List
$s=nub[n\\u<-inits s,n<-map(toInt o toString)(tails u)|n>1&&all(\m=n/m*m<n)[2..n-1]]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pyth, 8 bytes

fP_TsM.:

Test suite

Takes the input as a string, outputs a list of integers. Can also take input as an int by adding ` at the end for an extra byte.

Explanation:
fP_TsM.:  | Full code
fP_TsM.:Q |  with implicit variables added
          | Print (implicit)
      .:Q |  list of all substrings of the input
    sM    |   converted to integers
fP_T      |    filtered for prime numbers

And ` just converts int to str.

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 40 bytes

Select[PrimeQ@*FromDigits]@*Subsequences

Try it online!

Input and output are lists of digits. In the case of no prime subnumbers the empty list {} is returned.

Uses @* for Composition of functions. Subsequences gives a list of all subsequences of the input, and Select[PrimeQ@*FromDigits] is an operator form of Select which returns a list of all elements for which PrimeQ@*FromDigits returns True.

\$\endgroup\$
0
\$\begingroup\$

Matlab, 89 bytes

function[m]=f(x),m=1;for i=1:length(x),m=[m;str2num(combnk(x,i))];end,m=m(isprime(m));end

Try it Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.