En 1946, Erdos et Copeland ont prouvé qu'un certain nombre est un nombre normal , c'est-à-dire que les chiffres de son expansion décimale sont uniformément répartis.

Les utilisateurs entreront une séquence de chiffres et vous trouverez le plus petit nombre premier contenant cette chaîne dans la base 10.

Exemple:

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

Le code le plus court en octets gagne. Je sais que certains langages (mathématique, sage, pari-gp ...) sont livrés avec des fonctions intégrées liées aux nombres premiers. -50 octets si votre programme ne repose pas sur de telles fonctions. N'essayez pas de tricher à ce sujet s'il vous plaît, si votre langue a déjà un énorme avantage, ne réclamez pas le bonus.

Éditer

Selon quelques commentaires ci-dessous, le plus petit nombre premier contenant "03" est 3. Est-ce que cela fait vraiment une différence? La seule chose à laquelle je peux penser est que les nombres sont peut-être plus faciles à gérer que les chaînes.

Dans des cas comme "03", la sortie préférée serait 103. Cependant, je ne considère pas que ce soit la partie fondamentale de votre programme, vous êtes donc libre d'ignorer tout zéro de tête s'il vous accorde un nombre d'octets inférieur.

Golfscipt, 33 32 octets = -18 score

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

Explication:

• 2{...}{)}/- en commençant par 2, alors que quelque chose est vrai, incrémentez le haut de la pile

• ;;x- supprimer les valeurs intermédiaires collectées par {}{}/et l'entrée, puis y mettre la dernière valeur testée

• :x,2>- stocker la valeur sous x, puis produire une liste de 2àx-1

• {x\%!},!!- garder ceux qui xsont divisibles par, puis contraindre à booléen (non vide)
• x`3?)!- recherchez l'entrée sous forme de texte x( -1si elle n'est pas trouvée), incrémentez, annulez.
• | - ou

Programme Haskell, 97 caractères = 47 points

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

Fonction Haskell, 75 caractères = 25 points

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

le type de pest (Integral a, Show a) => [Char] -> a. Si vous fournissez votre propre type intégral, vous pouvez rechercher par infixe dans votre propre représentation de ces valeurs. La norme Integerutilise la notation décimale attendue pour les entiers.

Pas très vite. Quadratique dans la valeur (pas la taille) de la sortie.

version non golfée:

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

exemple:

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 caractères.

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)&

Timings relatifs sur mon Mac (i7 2,6 GHz avec 8 Go de mémoire).

Trouvez le plus petit nombre premier contenant "01".

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

{0.000217, 101}

Trouvez le plus petit nombre premier contenant "012345".

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

{5.021915, 10123457}

Trouvez le plus petit nombre premier contenant "0123456".

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

{87.056245, 201234563}

Sauge , 72

S'exécute dans l'invite interactive

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

Primes().unrank(i)donne le ie nombre premier, le 0e étant 2.

R, 56 caractères -50 = 6

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

Prenez l'entrée comme stdin. Incrémente k jusqu'à ce que k soit un nombre premier (testé en additionnant les instances pour lesquelles k mod 2 à k sont des zéros, donc FAUX puisque 0 transformé en logique est FAUX) et contient la chaîne donnée en entrée (testé avec un simple grep, ici grepl puisque nous voulons un résultat logique).

Usage:

> 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

Pas de définition d'une fonction ici ... juste un oneliner qui prend un argument $net scanne la plage entière (en fait un peu plus pour raccourcir le code). La version 55 caractères:

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

Ce n'est même pas trop lent. Pour n=0123456elle retourne 201234563dans 81.715s. C'est incroyablement rapide pour un long pipeline avec deux processeurs de chaînes.

En supprimant deux caractères (jusqu'à 53) et un canal, nous pouvons le faire fonctionner encore plus rapidement:

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

Et enfin, un peu de sedmagie pour le ramener à 45 caractères , bien que l'impression soit moche:

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

n = 000 -> 10007: 10007 (utilisateur 0,017s)

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

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

J - 38 caractères -50 = -12 pts

Normalement, en J, vous utiliseriez les fonctions intégrées très optimisées dédiées aux nombres premiers, donc je ne vais pas m'excuser pour la lenteur d'exécution.

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

Expliqué:

• >:@]^:(...)^:_&2- En commençant par 2, incrémentez jusqu'à ce que (...)renvoie false.
• (+.i.)@]- Prenez le GCD du compteur avec chaque entier plus petit que lui. (Nous utilisons la convention GCD (X, 0) = X.)
• ]=*/@- Prenez le produit de tous ces nombres et testez l'égalité au compteur. Si le compteur est premier, la liste était tous les 1, sauf pour le GCD avec 0; sinon, il y aura au moins un GCD supérieur à 1, donc le produit sera supérieur au compteur.
• >./@(E.":)- Testez si la représentation sous forme de chaîne du compteur ( ":) contient la chaîne ( E.) à tout moment. >./est la fonction max, et nous l'utilisons car E.retourne un vecteur booléen avec un 1 partout où la sous-chaîne commence dans la chaîne principale.
• *:- Logique NAND les résultats ensemble. Cela ne sera faux que si les deux entrées étaient vraies, c'est-à-dire si le compteur était à la fois premier et contenait la sous-chaîne.

Usage:

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

Pour la postérité, voici la version utilisant la prime intégrée (30 caractères de long, mais pas de bonus):

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

1 p:] teste le compteur pour la primauté, au lieu de l'astuce GCD.

Brachylog (v2), 3 octets dans l'encodage de Brachylog

ṗ≜s

Essayez-le en ligne!

Soumission de fonction, en prenant l'entrée de l'argument de droite, en donnant la sortie en mutant l'argument de gauche. (C'est l'opposé de la convention Brachylog normale; voir cette publication pour plus de détails. Changer les arguments dans l'ordre le plus courant coûterait trois octets.) Le lien TIO a un wrapper qui appelle la fonction avec la convention d'appel appropriée et imprime le résultat.

Explication

ṗ≜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}

Malheureusement, Brachylog est si approprié pour ce problème que selon les règles du problème, je ne peux même pas essayer d'aller chercher le bonus (ce qui signifie ironiquement qu'il est incapable de gagner).

L'une des raisons pour lesquelles j'aime tant Brachylog est que la programmation est une communication entre l'homme et l'ordinateur, et donc un langage "parfait" vous permettrait de traduire directement la spécification du problème en anglais directement; les idées par lesquelles le problème a été énoncé et par lesquelles le programme est écrit seraient les mêmes. Brachylog peut atteindre cet idéal étonnamment souvent; la question ici est "trouver le plus petit nombre premier contenant une sous-chaîne donnée", et je peux littéralement enchaîner les concepts de "plus petit, premier, contenant la sous-chaîne" dans le bon ordre et avoir un programme de travail. En tant que tel, Brachylog en dit beaucoup plus sur la nature de la communication qu'un langage dans lequel vous deviez explicitement spécifier un algorithme pour résoudre le problème; parfois quand on parle à d'autres humains, nous essayons d'expliquer un problème en expliquant les étapes à suivre pour le résoudre, mais c'est rare. Alors pourquoi nos langues devraient-elles être différentes?

JavaScript 83 octets = 33 points

Golfé:

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)

Non golfé (un peu):

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 octets = 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}

Sous forme extraite avec des noms de variables sensibles:

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

Rouille 0,9 136 octets = 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);
}

Très explicite malgré sa compacité. Trop d'espace dépensé pour la recherche de chaîne. :(

Voici la version sans espace (136 caractères)

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

Japt, 10 octets

_j *ZsøU}a

Essayez-le

Tidy , 37 octets

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

Essayez-le en ligne!

Perl 6 , 36 - 50 = -14 points

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

Essayez-le en ligne!

Considérant $_%%one ^$_que les 2 seuls octets sont plus petits que .is-prime, je pense que cela en vaut la peine pour le bonus. Cela expire pour le dernier cas de test.

Explication:

{                                  }  # 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 octets - 50 = 30 29 score

-1 octet grâce à l'utilisation créative de @ ASCII uniquement au %slieu destr

Le cas de test "98765" n'a pas encore été confirmé en raison du temps qu'il faut pour tester Confirmé pour le cas de test "98765" après quelques heures, mais avec une approche similaire qui utilise une évaluation en court-circuit pour éviter certains tests de primalité, cela fonctionne Plus vite. Alternativement, cela peut être ~ 2x plus rapide si nous savons que "2" n'est pas une entrée (nous pouvons éviter de vérifier les nombres pairs pour la primauté) en définissant i=3initialement et i+=2dans la boucle, sans coût supplémentaire en octets.

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

Essayez-le en ligne!

Explication de la whilecondition ( (x in"%s"%i)*all(i%j for j in range(2,i))-1):

(x in"%s"%i): True/ 1si le compteur actuel contient la séquence de nombres souhaitée; False/ 0sinon.

all(i%j for j in range(2,i)): True/ 1si le compteur courant a toujours un reste lorsqu'il est divisé par un entier de 2 (inclus) à lui-même (exclusif), c'est-à-dire qu'il est premier; False/ 0sinon.

Le *multiplie les deux conditions ensemble et agit comme un andopérateur - le produit est True/ 1si et seulement si les deux conditions sont True/ 1.

L' opérateur -1agit comme un notopérateur: False/ 0- 1 donne -1, ce qui est considéré comme vrai, tandis que True/ 1- 1 entraîne 0, ce qui est considéré comme faux. Ainsi, la boucle continue tandis que le nombre ne contient pas la séquence de nombres souhaitée ou n'est pas premier.

Remplacez le *par andet ajoutez des parenthèses autour de tout sauf -1pour une solution équivalente beaucoup plus rapide (qui est légèrement plus longue).

Une solution de score de 76 octets - 50 = 26 en Python 2 donnée par @ ASCII uniquement (utilise à la ``place de str(),

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

Essayez-le en ligne!

JavaScript, 65 - 50 = 15 points

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

Essayez-le en ligne!