Imprimer le nième nombre premier qui contient n

39

Cette question sera un tournant dans la recherche du nnombre premier th.

Défi

Vous devez écrire un programme qui prendra une entrée net sortir le nnombre premier dont la représentation décimale contient la représentation décimale de nsous-chaîne.

Confus? Voici quelques exemples.

n=1
Primes: 2, 3, 5, 7, 11
                    ^1 first prime that contains a 1
Output: 11

n=2
Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23
        ^1                          ^2 second prime that contains a 2
Output: 23

n=3
Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23
           ^1           ^2          ^3 third prime that contains a 3
Output: 23

n=10
Primes: 2, 3, 5, 7, 11, ..., 97, 101, 103, 107, 109, ..., 997, 1009, 1013, 1019, 1021, 1031, 1033
                                 ^1   ^2   ^3   ^4             ^5    ^6    ^7    ^8    ^9    ^10 tenth prime that contains a 10
Output: 1033

C'est le , donc le plus petit nombre d'octets gagne.

Si quelque chose est déroutant, laissez s'il vous plaît un commentaire.

ericw31415
la source
2
Existe-t-il un OEIS pour cela? On a l'impression qu'il devrait y avoir
MayorMonty
@SpeedyNinja Non, j'ai déjà vérifié.
Adnan
Connexes
Alex A.
1
Je ne peux pas croire que cela a fait le numéro 5 sur la Hot Network Questionsliste.
ericw31415
Une séquence similaire
Nathan Merrill

Réponses:

12

05AB1E , 8 octets

Code:

µN¹åNp*½

Explication:

µ          # Run this until the counting variable has reached the input value.
 N¹å       # Check if the input number is in the range variable.
    Np     # Check if the range variable is prime.
      *    # Multiply those two numbers (which is basically an AND operator).
       ½   # If true, increment the counting variable.
           # After the loop, the stack is empty and implicitly prints N.

Utilise le CP-1252 codage . Essayez-le en ligne! .

Adnan
la source
10

Pyth - 11 octets

e.f&P_Z}`Q`

Suite de test .

Maltysen
la source
8

Python 2, 67 65 62 octets

f=lambda n,k=0,m=2,p=1:k/n or-~f(n,k+p%m*(`n`in`m`),m+1,p*m*m)

Testez-le sur Ideone .

Comment ça marche

Nous utilisons un corollaire du théorème de Wilson :

corollaire du théorème de Wilson

En tout temps, la variable p est égale au carré de la factorielle de m - 1 .

Si k <n , k/ndonnera 0 et f est appelé récursivement. m est incrémenté, p est mis à jour et k est incrémenté si et seulement si m est un nombre premier qui contient n .

Ce dernier est obtenu en ajoutant le résultat de p%m*(`n`in`m`)à k . Selon le corollaire du théorème de Wilson, si m est premier, p%mretourne 1 et sinon, il retourne 0 .

Une fois que k atteint n , nous avons trouvé q , le n e premier qui contient n .

Nous sommes dans le prochain appel pendant le contrôle, donc m = q + 1 . k/nrenverra 1 et les opérateurs au niveau du bit -~incrémenteront ce nombre une fois pour chaque appel de fonction. Comme il faut q - 1 appels à f pour incrémenter m de 2 à q + 1 , l'appel le plus à l'extérieur de f renverra 1 + q - 1 = q , comme prévu.

Dennis
la source
6

Bash, 27 octets

primes 0|grep $1|sed $1q\;d

primes vient de bsdgames.

Prend l'entrée en tant qu'argument de ligne de commande et sort sur STDOUT.

Poignée de porte
la source
4

Mathematica, 75 octets

Nest[NestWhile[b=NextPrime,b@#,!StringContainsQ@@ToString/@{#,a}&]&,1,a=#]&

Peut encore être golfable.

LegionMammal978
la source
C'est probablement la solution la plus rapide car elle utilise NextPrime :)
4

Java, 194 180 173 171 112 Octets

Code:

a->{int i=1,j,n,r=0;for(j=n=new Integer(a);(r+=++i>=j&(""+j).contains(""+n)?1:0)!=n;j+=j%i==0?i=1:0);return j;}

Ungolfed:

class P{
    static int i=1,j,n,r;
    public static void main(String[]s) {
        for(
                j=n=new Integer(s[0]); //executes once before first iteration
                (r+=++i>=j&(""+j).contains(""+n)?1:0)!=n; //executes on first and every iteration
                j+=j%i==0?i=1:0 //executes after first and every iteration
           ) {
            ;
        }
        System.out.print(j);
    }
}
Si tout va bien utile
la source
Bonjour, bienvenue sur PPCG! Deux choses à noter, 1. Vous pouvez supprimer deux espaces à P {et String[] s. Et vous ne donnez actuellement que la sortie 10, mais le défi code-golf consistait à prendre une entrée net à donner la sortie appropriée en fonction de cette entrée. En outre, cela pourrait vous intéresser: des astuces pour jouer au golf en Java.
Kevin Cruijssen
3

Ruby, 62 61 octets

->i{Prime.lazy.map(&:to_s).grep(/#{i}/).first(i)[-1]}

Nécessite le -rprimedrapeau (+8 octets).

->i{            # lambda with one argument
Prime           # iterator over all primes
.lazy           # make the iterator lazy (can't evaluate infinite primes)
.map(&:x.to_s)  # convert the primes to strings
.grep(/#{i}/)   # find primes that regex match on the input (contain it)
.first(i)       # take the first (input) primes that satisfy this
[-1]            # take the last of those
}
Poignée de porte
la source
3

MATL , 18 octets

`@YqVGVXf?3M]NG<]&

Essayez-le en ligne!

Explication

Cela génère des nombres premiers dans l'ordre à l'aide d'une do...whileboucle. Pour chaque prime, la condition est testée (et la prime est consommée). S'il est satisfait, ce nombre premier est à nouveau placé dans la pile. Le nombre d'éléments dans la pile est utilisé pour compter le nombre de nombres premiers qualifiants que nous avons trouvés. Quand il y en a assez, le dernier est affiché.

`         % Do...while
  @       %   Push iteration index, k. Starts at 1
  YqV     %   k-th prime. Convert to string
  GV      %   Push input, n. Convert to string
  Xf      %   Find string within another
  ?       %   If non-empty
    3M    %     Push k-th prime again (increase stack size by 1)
  ]       %   End if
  NG<     %   Is stack size less than input number? If so proceeed with
          %   a new iteration; else exit do...while loop
]         % End do...while
&         % Implicitly display only top number in the stack 
Luis Mendo
la source
1

Bash + coreutils GNU, 66 octets

Contrairement à la solution de @ Doorknob, celle-ci ne nécessite que les éléments installés sur chaque système GNU / Linux:

for((n=2;;n++)){
[ `factor $n|wc -w` -eq 2 ]&&grep $1<<<$n&&exit
}
rexkogitans
la source
seq 1e20|factor|grep -Po "(?<=: )\d*$2\d$"|sed $1q\;d
Digital Trauma
@ DigitalTrauma, mon cerveau ne fonctionne pas de cette façon ;-)
rexkogitans
A-t-il besoin des nouvelles lignes?
ericw31415
Après for((...)){, il doit y avoir un espace ou une nouvelle ligne, donc ce n'est pas grave. Avant la fermeture }, il doit y avoir une ; ou une nouvelle ligne, donc cela n'a pas d'importance non plus.
rexkogitans
1

Perl 6 , 41 octets

->$n {grep({.is-prime&&/$n/},2..*)[$n-1]}

Explication:

-> $n { # has one parameter
  grep(
    {
      .is-prime # check that it is prime
      &&        # and
      / $n /    # that it contains the argument in the "string"
    },
    2 .. *      # for all numbers starting with 2
  )[ $n - 1 ]   # only take the $n-th one
                # ( accounting for 0 based array access )
}

Tester:

#! /usr/bin/env perl6
use v6.c;
use Test;

my &prefix:<ℙ𝕟> = ->$n {grep({.is-prime&&/$n/},2..*)[$n-1]}

my @test = (
  1  => 11,
  2  => 23,
  3  => 23,
  10 => 1033,
);

plan +@test;

for @test {
  is ℙ𝕟.key, .value, .gist
}
1..4
ok 1 - 1 => 11
ok 2 - 2 => 23
ok 3 - 3 => 23
ok 4 - 10 => 1033
Brad Gilbert b2gills
la source
1

Java 8, 192 183 181 171 octets (programme complet)

interface M{static void main(String[]a){long n=new Long(a[0]),c=0,r=1,m,i;for(;c<n;c+=m>1&(r+"").contains(a[0])?1:0)for(m=++r,i=2;i<m;m=m%i++<1?0:m);System.out.print(r);}}

Essayez-le en ligne.

Explication:

interface M{                    // Class
  static void main(String[]a){  //  Mandatory main-method
    long n=new Long(a[0]),      //   Input argument as number
         c=0,                   //   Counter, starting at 0
         r=1,                   //   Result-number, starting at 1
         m,i;                   //   Temp number
    for(;c<n;                   //   Loop as long as `c` does not equals `n`
        c+=                     //     After every iteration: increase `c` by:
           m>1                  //      If the current `r` is a prime,
           &(r+"").contains(a[0])?
                                //      and this prime contains the input `n`
            1                   //       Increase `c` by 1
           :                    //      Else:
            0)                  //       Leave `c` the same
      for(m=++r,                //    Increase `r` by 1 first with `++r`, and set `m` to it
          i=2;i<m;              //    Inner loop `i` in the range [2, `m`)
        m=m%i++<1?              //     If `m` is divisible by `i`
           0                    //      Change `m` to 0 (so it's not a prime)
          :                     //     Else:
           m);                  //      Leave `m` unchanged
    System.out.print(r);}}      //    Print `r` as result

Java 8, 105 octets (fonction lambda)

n->{int c=0,r=1,m,i;for(;c<n;c+=m>1&(r+"").contains(n+"")?1:0)for(m=++r,i=2;i<m;m=m%i++<1?0:m);return r;}

Essayez-le en ligne.

Comme ci-dessus, mais avec une nentrée entière et sans les éléments de classe prolixe.

Kevin Cruijssen
la source
1
vous pouvez remplacer &&avec &et retirer ?de votre regexp.
Cliffroot
@cliffroot Merci, édité le post. J'oublie toujours &&et &pour une raison quelconque ..
Kevin Cruijssen
0

Clojure, 118 octets

(defn s[n](nth(filter(fn[x](if(.contains(str x)(str n))(not-any? #(=(mod x %)0)(range 2 x))))(drop 2(range)))(dec n)))

Obtient simplement le nième élément d'une suite infinie paresseuse de nombres qui sont premiers et qui ont nune représentation sous forme de chaîne.

Vous pouvez l'essayer ici: https://ideone.com/ioBJjt

cliffroot
la source
0

En fait, 16 octets

;$╗`P$╜@íu`╓dP.X

Essayez-le en ligne!

Explication:

;$╗`P$╜@íu`╓dP.X
;$╗               make a copy of n, push str(n) to reg0
   `      `╓      push the first n values where f(k) is truthy, starting with k=0:
    P$              kth prime, stringified
      ╜@íu          1-based index of n, 0 if not found
            d     remove last element of list and push it to the stack (dequeue)
             P    nth prime
              .   print
               X  discard rest of list
Mego
la source
0

PowerShell v2 +, 108 99 octets

Ooof. L'absence de tout type de calcul / vérification prime intégré fait vraiment mal ici.

param($n)for(){for(;'1'*++$i-match'^(?!(..+)\1+$)..'){if("$i"-like"*$n*"){if(++$o-eq$n){$i;exit}}}}

Prend entrée $n, entre dans une for()boucle infinie . À chaque itération, nous utilisons une forboucle entourant le vérificateur principal de regex de PowerShell (h / t to Martin) pour le transformer en un générateur de nombres premiers en incrémentant$i chaque fois dans la boucle. (Par exemple, si vous ne faites que for(){for(;'1'*++$i-match'^(?!(..+)\1+$)..'){$i}}lancer2, 3, 5, 7... séparée par des nouvelles lignes).

Ensuite, une simple -likevérification pour voir si $nest quelque part $i, et incrémenter notre compteur $o. Si nous avons atteint où $net $osommes égaux, sortie $iet exit. Sinon, nous continuons forà chercher le prochain nombre premier et le processus se répète.

AdmBorkBork
la source
0

APL (NARS), 39 caractères, 78 octets

{s←⍕w←⍵⋄2{(w≤⍵)∧k←∨/s⍷⍕⍺:⍺⋄(1π⍺)∇⍵+k}1}

1π est le prochain nombre premier ...; tester:

  f←{s←⍕w←⍵⋄2{(w≤⍵)∧k←∨/s⍷⍕⍺:⍺⋄(1π⍺)∇⍵+k}1}
  f¨1 2 3 10
11 23 23 1033 

mais cela a déjà 20 ans sort de la pile ... Au lieu de cela, ça semble correct même si la longueur est un peu plus longue (61 caractères)

∇r←f w;i;k;s
r←2⋄s←⍕w⋄i←1
→0×⍳(w≤i)∧k←∨/s⍷⍕r⋄r←1πr⋄i+←k⋄→2
∇

  f¨1 2 3 10 20 100
11 23 23 1033 4201 100999 
RosLuP
la source
0

Ajouter ++ , 36 octets

L,5*2^RßÞPABDBJVB]dG€Ωezߣ*BZB]A1_$:

Essayez-le en ligne!

Assez inefficace. Itère sur chaque entierje tel que je25X2 et filtre les composites et les nombres premiers qui ne contiennent pas n. Enfin, nous prenons lene valeur des entiers restants.

caird coinheringaahing
la source