# Find the smallest prime from a substring

In 1946 Erdos and Copeland proved that a certain number is a normal number, i.e. the digits in its decimal expansion are uniformly distributed.

Users will input a sequence of digits and you will find the smallest prime that contains that string in base 10.

Example:

``````input   -> output
"10"    -> 101
"03"    -> 103
"222"   -> 2221
"98765" -> 987659
``````

Shortest code in bytes wins. I do know that some languages (mathematica, sage, pari-gp...) come with built-in functions related to primes. -50 bytes if your program doesn't rely on such functions. Don't try to cheat on this please, if your language already has a huge advantage don't claim the bonus.

## Edit

According to a few comments below, the smallest prime that contains "03" is 3. Does this really make a difference? The only thing I can think of is that maybe numbers are easier to handle than strings.

In cases like "03" the preferred output would be 103. However, I don't consider it to be the fundamental part of your program, so you're free to ignore any leading zero if it grants you a lower byte count.

-
This seems like a nice base for a Project Euler task – Jan Dvorak Mar 5 '14 at 6:18
The smallest prime containing "03" is 03. Maybe you should add a rule clarifying that the input may contain leading zeros but the output may not. – Level River St Mar 5 '14 at 9:55
@steveverrill there's no such number as 03. If you meant 3, then that doesn't contain "03". – Jan Dvorak Mar 5 '14 at 10:02
@JanDvorak 03 is a valid representation of the number 3. (2.9... recurring infinitely, equivalent to 2+9/9, is also considered by some a valid representation.) I understand from the example given that 03 is not an acceptable representation for this question. This is a pedant point, but given the usual abuse of the rules, one I think is worth making. – Level River St Mar 5 '14 at 10:19
I think the better way to phrase it would be to find the smallest number that, when converted to a string, would contain "03". – Thebluefish Mar 5 '14 at 15:26

# Golfscipt, 33 32 bytes = -18 score

``````2{:x,2>{x\%!},!!x`3\$?)!|}{)}/;;x
``````

Explanation:

• `2{...}{)}/` - starting with `2`, while something is true, increment the top of the stack
• `;;x` - discard the intermediate values collected by `{}{}/` and the input, then put the last value tested there

• `:x,2>` - store the value as `x`, then produce a list from `2` to `x-1`

• `{x\%!},!!` - keep those that `x` is divisible by, then coerce to boolean (not empty)
• `x`3?)!` - look up the input in the text form of `x` (`-1` if not found), increment, negate.
• `|` - or
-

### Haskell program, 97 characters = 47 score

``````main=getLine>>= \i->print\$head\$[x|x<-[2..],all((/=0).mod x)[2..x-1],i`Data.List.isInfixOf`show x]
``````

### Haskell function, 75 characters = 25 score

``````p i=head\$[x|x<-[2..],all((/=0).mod x)[2..x-1],i`Data.List.isInfixOf`show x]
``````

the type of `p` is `(Integral a, Show a) => [Char] -> a`. If you supply your own integral type, you can lookup by infix in your own representation of those values. The standard `Integer` uses the expected decimal notation for integers.

Not very fast. Quadratic in the value (not size) of the output.

ungolfed version:

``````import Data.List
leastPrime infix = head \$ filter prime' [2..]
where prime' x  = all (\n-> x`mod`n /= 0) [2..x-1]
&& i `isInfixOf` show x
main = print . leastPrime =<< getLine
``````

example:

``````Prelude> let p i=head\$[x|x<-[2..],all((/=0).mod x)[2..x-1],i`Data.List.isInfixOf`show x]
Prelude> p "0"
101
Prelude> p "00"
1009
Prelude> p "000" -- long pause
10007
``````
-

Java - 175 characters.

``````class s{public static void main(String[]a){int i,n=2,p;for(;;){p=1;for(i=3;i<n;i++)if(n%i==0)p=0;if((n==2||p>0)&&(""+n).indexOf(a[0])>=0) {System.out.println(n);break;}n++;}}}
``````
-
You can save 1 character by dropping the space between `indexOf(a[0])>=0)` and `{System.out.println(n)`. – ProgramFOX Mar 5 '14 at 7:54
@ProgramFOX Thanks. – wildcard Mar 5 '14 at 8:08
I think you can easily save (about 8) characters by replacing your `boolean p=true` by something like `int p=1` and so on. – florian h Mar 5 '14 at 10:13
declaring all your ints at once will further reduce your program size. – Olivier Grégoire Mar 5 '14 at 13:54
@florian Thanks, fixed. – wildcard Mar 5 '14 at 16:36

# Mathematica 58

``````(n = 1; While[StringCases[ToString[p = Prime@n], #] == {}, n++]; p) &
``````

Relative Timings on my Mac (2.6 GHz i7 with 8 GB memory).

Find the smallest prime containing "01".

``````AbsoluteTiming[(n = 1; While[StringCases[ToString[p = Prime@n], #] == {}, n++]; p) &["01"]]
``````

{0.000217, 101}

Find the smallest prime containing "012345".

``````AbsoluteTiming[(n = 1; While[StringCases[ToString[p = Prime@n], #] == {}, n++]; p) &["012345"]]
``````

{5.021915, 10123457}

Find the smallest prime containing "0123456".

``````AbsoluteTiming[(n = 1; While[StringCases[ToString[p = Prime@n], #] == {}, n++]; p) &["0123456"]]
``````

{87.056245, 201234563}

-
You can use `StringFreeQ` to make it shorter. – alephalpha Mar 7 '14 at 4:32

# Sage, 72

Runs in the interactive prompt

``````a=raw_input()
i=0
p=2
while a not in str(p):i+=1;p=Primes().unrank(i)
p
``````

`Primes().unrank(i)` gives the `i`th prime number, with the 0th prime being 2.

-

### R, 56chars -50 = 6

``````k=2;n=scan(,"");while(!grepl(n,k)|sum(!k%%2:k)>1)k=k+1;k
``````

Take input as stdin. Increments k until k is a prime (tested by summing the instances for which k mod 2 to k are zeroes, hence FALSE since 0 turned into a logical is FALSE) and contains the string given as input (tested with a simple grep, here grepl since we want a logical as result).

Usage:

``````> k=2;n=scan(,"");while(!grepl(n,k)|sum(!k%%2:k)>1)k=k+1;k
1: "03"
2:
[1] 103
> k=2;n=scan(,"");while(!grepl(n,k)|sum(!k%%2:k)>1)k=k+1;k
1: "003"
2:
[1] 2003
``````
-

# shell oneliner (coreutils): 45chars

Not defining a function here... just a oneliner that takes one argument in `\$n` and scans the integer range (actually a bit more to make code shorter). The 55 character version:

``````seq 5e9|grep \$n|factor|awk '{if(NF==2)print \$2}'|head -n1
``````

It's not even too slow. For `n=0123456` it returns `201234563` in `81.715s`. That's impressively fast for a long pipeline with two string processors.

Removing two characters (down to 53) and one pipe, we can get it running even faster:

``````seq 5e9|grep \$n|factor|awk '{if(NF==2){print \$2;exit}}'
``````

And finally, some `sed` wizardry to bring it down to 45 characters, although the printout is ugly:

``````seq 5e9|grep \$n|factor|sed -n '/: \w*\$/{p;q}'
``````

n=000 -> 10007: 10007 (user 0.017s)

n=012345 -> 10123457: 10123457 (user 7.11s)

n=0123456 -> 201234563: 201234563 (user 66.8s)

-

# JavaScript 83 bytes = 33 score

Golfed:

``````for(s=prompt(n=x=0);!n;x++)for(n=(''+x).match(s)?2:0;n&&n<x;n=x%n?n+1:0);alert(x-1)
``````

Ungolfed (a bit):

``````s=prompt() // get the input
n = 0
for(x=0;!n;x++) // stop when n is non-zero
if ((''+x).match(s)) { // if x matches the pattern, check if x is prime
for(n=2;n&&n<x;)
n = (x%n == 0) ? 0 : n+1; // if x%n is zero, x is not prime so set n=0
// if n is non-zero here, x is prime and matches the pattern
}
``````
-

# J - 38 char -50 = -12 pts

Normally in J, you'd be using the very optimized builtins dedicated to primes, so I'm not going to apologize for any slowness in execution.

``````>:@]^:(>./@(E.":)*:]=*/@(+.i.)@])^:_&2
``````

Explained:

• `>:@]^:(...)^:_&2` - Starting with 2, increment until `(...)` returns false.
• `(+.i.)@]` - Take the GCD of the counter with every integer smaller than it. (We use the convention GCD(X,0) = X.)
• `]=*/@` - Take the product of all these numbers, and test for equality to the counter. If the counter is prime, the list was all 1s, except for the GCD with 0; else there will be at least one GCD that is greater than 1, so the product will be greater than the counter.
• `>./@(E.":)` - Test if the string representation of the counter (`":`) contains the string (`E.`) at any point. `>./` is the max function, and we use it because `E.` returns a boolean vector with a 1 wherever the substring begins in the main string.
• `*:` - Logical NAND the results together. This will be false only if both inputs were true, i.e. if the counter both was prime and contained the substring.

Usage:

``````   >:@]^:(>./@(E.":)*:]=*/@(+.i.)@])^:_&2 '03'
103
>:@]^:(>./@(E.":)*:]=*/@(+.i.)@])^:_&2 '713'
2713
``````

For posterity, here's the version using the prime builtin (30 char long, but no bonus):

``````>:@]^:(>./@(E.":)*:1 p:])^:_&2
``````

`1 p:]` tests the counter for primality, instead of the GCD trick.

-

# Javascript (Node.JS) - 93 bytes = 43 points

``````l:for(i=x=process.argv[2];j=i;i++){while(--j>2)if(!(i%j*(""+i).match(x)))continue l
throw i}
``````

In extracted form with sensible variable names:

``````outerLoop:for (currentTry=inputNumber=process.argv[2]; primeIterator=currentTry; currentTry++ ) {
while (--primeIterator > 2)
if(!(currentTry % primeIterator * (""+currentTry).match(inputNumber)))
continue outerLoop;
throw i
}
``````
-

# Rust 0.9 136 bytes = 86 points

``````fn main(){
let mut n:u32=2;
while n.to_str().find_str(std::os::args()[1])==None ||
range(2,n).find(|&x|n%x==0)!=None {
n=n+1;
}
print!("{}",n);
}
``````

Very explicit despite for compactness. Too much space spent on the string find. :(

Here the version without whitespace (136 char)

``````fn main(){let mut n:u32=2;while n.to_str().find_str(std::os::args()[1])==None||range(2,n).find(|&x|n%x==0)!=None{n=n+1;}print!("{}",n);}
``````
-