Em 1946, Erdos e Copeland provaram que um determinado número é um número normal , ou seja, os dígitos em sua expansão decimal são distribuídos uniformemente.

Os usuários digitarão uma sequência de dígitos e você encontrará o menor primo que contém essa sequência na base 10.

Exemplo:

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

O menor código em bytes vence. Eu sei que algumas linguagens (mathematica, sage, pari-gp ...) vêm com funções internas relacionadas a números primos. -50 bytes se o seu programa não contar com essas funções. Não tente trapacear, por favor, se o seu idioma já tiver uma grande vantagem, não reivindique o bônus.

Editar

De acordo com alguns comentários abaixo, o menor primo que contém "03" é 3. Isso realmente faz alguma diferença? A única coisa em que consigo pensar é que talvez os números sejam mais fáceis de lidar do que as strings.

Em casos como "03", a saída preferida seria 103. No entanto, não considero que seja a parte fundamental do seu programa, portanto, você pode ignorar qualquer zero inicial se isso lhe conceder uma contagem de bytes mais baixa.

Golfscipt, 33 32 bytes = -18 pontuação

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

Explicação:

• 2{...}{)}/- começando com 2, enquanto algo é verdadeiro, incrementa o topo da pilha

• ;;x- descarte os valores intermediários coletados por {}{}/e pela entrada e, em seguida, coloque o último valor testado lá

• :x,2>- armazene o valor como e x, em seguida, produza uma lista de 2parax-1

• {x\%!},!!- mantenha aqueles que xsão divisíveis por, então coagir ao booleano (não vazio)
• x`3?)!- procure a entrada no formato de texto de x( -1se não for encontrado), incremente, negue.
• | - ou

Programa Haskell, 97 caracteres = 47 pontos

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

Função Haskell, 75 caracteres = 25 pontos

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

o tipo de pé (Integral a, Show a) => [Char] -> a. Se você fornecer seu próprio tipo integral, poderá procurar por infixo em sua própria representação desses valores. O padrão Integerusa a notação decimal esperada para números inteiros.

Não é muito rápido. Quadrático no valor (não no tamanho) da saída.

versão não destruída:

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

exemplo:

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 caracteres.

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++;}}}

Mathematica 58

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

Tempos relativos no meu Mac (2,6 GHz i7 com 8 GB de memória).

Encontre o menor primo contendo "01".

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

{0,000217, 101}

Encontre o menor primo contendo "012345".

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

{5.021915, 10123457}

Encontre o menor primo contendo "0123456".

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

{87.056245, 201234563}

Sálvia , 72

Executa no prompt interativo

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

Primes().unrank(i)dá o ith número primo, com o 0º primo sendo 2.

R, 56 caracteres -50 = 6

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

Tome a entrada como stdin. Incrementa k até que k seja primo (testado somando as instâncias para as quais k mod 2 e k são zeros, portanto, FALSO desde que 0 se transformou em um lógico é FALSE) e contém a string fornecida como entrada (testada com um grep simples, aqui grepl já que queremos um resultado lógico).

Uso:

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

shell oneliner (coreutils): 45chars

Não definindo uma função aqui ... apenas um oneliner que pega um argumento $ne varre o intervalo inteiro (na verdade, um pouco mais para tornar o código mais curto). A versão de 55 caracteres:

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

Não é nem muito lento. Pois n=0123456ele retorna 201234563em81.715s . Isso é impressionantemente rápido para um pipeline longo com dois processadores de string.

Removendo dois caracteres (até 53) e um canal, podemos executá-lo ainda mais rápido:

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

E finalmente, algumas sedmagias para reduzi-lo a 45 caracteres , embora a impressão seja feia:

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

n = 000 -> 10007: 10007 (usuário 0,017s)

n = 012345 -> 10123457: 10123457 (usuário 7.11s)

n = 0123456 -> 201234563: 201234563 (usuário 66,8s)

J - 38 char -50 = -12 pts

Normalmente, em J, você usaria os recursos internos muito otimizados dedicados a números primos, por isso não vou me desculpar por qualquer lentidão na execução.

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

Explicado:

• >:@]^:(...)^:_&2- Começando com 2, incremente até (...)retornar falso.
• (+.i.)@]- Pegue o GCD do contador com cada número inteiro menor que ele. (Usamos a convenção GCD (X, 0) = X.)
• ]=*/@- Leve o produto de todos esses números e teste a igualdade no balcão. Se o contador for primo, a lista era todos os 1s, exceto o GCD com 0; caso contrário, haverá pelo menos um GCD maior que 1; portanto, o produto será maior que o contador.
• >./@(E.":)- Teste se a representação de string do contador ( ":) contém a string ( E.) em qualquer ponto. >./é a função max, e a usamos porqueE. retorna um vetor booleano com 1 onde quer que a substring comece na string principal.
• *:- NAND lógico os resultados juntos. Isso será falso apenas se as duas entradas forem verdadeiras, ou seja, se o contador for primo e contiver a substring.

Uso:

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

Para a posteridade, aqui está a versão usando o builtin principal (30 caracteres, mas sem bônus):

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

1 p:] testa o contador em busca de primalidade, em vez do truque da GCD.

Brachylog (v2), 3 bytes na codificação de Brachylog

ṗ≜s

Experimente online!

Submissão de funções, recebendo entrada do argumento do lado direito, produzindo uma mutação do argumento do lado esquerdo. (Isso é o oposto da convenção Brachylog normal; consulte esta meta post para obter mais discussões. Trocar os argumentos na ordem mais usual custaria três bytes.) O link TIO possui um invólucro que chama a função com a convenção de chamada apropriada e imprime o resultado.

Explicação

ṗ≜s
 ≜   Find the integer closest to zero
ṗ      which is prime {implicit: and output it via the left argument}
  s    and which is a substring of the {right argument}

Infelizmente, Brachylog é tão apropriado para esse problema que, de acordo com as regras do problema, eu não posso nem tentar obter o bônus (o que ironicamente significa que é incapaz de vencer).

Uma das razões pelas quais eu gosto tanto do Brachylog é que a programação é uma comunicação entre humanos e computadores e, portanto, uma linguagem "perfeita" permite traduzir a especificação do problema diretamente para o inglês; as idéias através das quais o problema foi declarado e através das quais o programa foi escrito seriam as mesmas. Brachylog pode atingir esse ideal surpreendentemente com frequência; a pergunta aqui é "encontre o menor primo que contém uma determinada substring" e eu posso literalmente agrupar os conceitos de "menor primo, contendo substring" na ordem correta e ter um programa de trabalho. Como tal, Brachylog diz muito mais sobre a natureza da comunicação do que uma linguagem na qual você tinha que especificar explicitamente um algoritmo para resolver o problema; às vezes quando conversamos com outros humanos, tentamos explicar um problema, explicando as etapas que você executaria para resolvê-lo, mas isso é raro. Então, por que nossas línguas devem ser diferentes?

JavaScript 83 bytes = 33 pontos

Golfe:

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 (um pouco):

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
    }
alert(x-1)

Javascript (Node.JS) - 93 bytes = 43 pontos

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

Na forma extraída com nomes de variáveis ​​sensíveis:

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

Ferrugem 0,9 136 bytes = 86 pontos

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);
}

Muito explícito, apesar de compacto. Muito espaço gasto na localização de strings. :(

Aqui a versão sem espaço em branco (136 caracteres)

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);}

Japonês, 10 bytes

_j *ZsøU}a

Tente

Arrumado , 37 bytes

{s:s&{s,p:s in"".p}from primes|first}

Experimente online!

Perl 6 , 36 - 50 = -14 pontos

{$^a;first {/$a/&&$_%%one ^$_},2..*}

Experimente online!

Considerando que $_%%one ^$_são apenas os 2 bytes menores que .is-prime, acho que vale a pena pelo bônus. Isso expira para o último caso de teste.

Explicação:

{                                  }  # Anonymous code block
 $^a;                                 # Assign input to $a
     first                    ,2..*   # Find the first number
           {                 }        # Which
            /$a/                        # Contains the input
                &&                      # And
                  $_%%one ^$_           # Is prime

Python 3 , 80 79 bytes - 50 = 30 29 pontos

-1 byte graças ao uso criativo de @ ASCII-only em %svez destr

O caso de teste "98765" ainda não foi confirmado devido ao tempo que leva para testar. Confirmado para o caso de teste "98765" após algumas horas, mas com uma abordagem semelhante que utiliza avaliação de curto-circuito para evitar alguns testes de primalidade, ele funciona. muito mais rapido. Como alternativa, isso pode ser ~ 2x mais rápido se soubermos que "2" não é uma entrada (podemos evitar a verificação de números pares para primalidade) configurando i=3inicialmente e i+=2no loop, sem custo adicional de bytes.

def f(x):
 i=2
 while(x in"%s"%i)*all(i%j for j in range(2,i))-1:i+=1
 return i

Experimente online!

Explicação da whilecondição ( (x in"%s"%i)*all(i%j for j in range(2,i))-1):

(x in"%s"%i): True/ 1se o contador atual contiver a seqüência desejada de números; False/ 0caso contrário.

all(i%j for j in range(2,i)): True/ 1se o contador atual sempre tiver um restante quando dividido por qualquer número inteiro de 2 (inclusive) para si mesmo (exclusivo), ou seja, é primo; False/ 0caso contrário.

o * multiplica as duas condições e atua como andoperador - o produto é True/ 1se e somente se as duas condições forem True/ 1.

A -1atua como um notoperador:False / 0- 1 resultados em -1, que é considerada verdadeira, ao passo que True/ 1- 1 resultados em 0, que é considerada falsa. Assim, o loop continua enquanto o número não contém a sequência desejada de números ou não é primo.

Substitua *por ande adicione parênteses em torno de tudo, exceto o-1 para uma solução equivalente muito mais rápida (que é um pouco mais longa).

Uma solução de pontuação de 76 bytes - 50 = 26 no Python 2 fornecida por @ ASCII-only (utiliza em ``vez destr() ,

def f(x):
 i=2
 while(x in`i`)*all(i%j for j in range(2,i))-1:i+=1
 return i

Experimente online!

JavaScript, 65 - 50 = 15 pontos

x=>(f=y=>(''+y).match(x)&&(p=n=>--n<2||y%n&&p(n))(y)?y:f(y+1))(x)

Experimente online!