Est-ce que ce nombre est un nombre premier?

195

Croyez-le ou non, nous n'avons pas encore de défi de code de golf pour un simple test de primalité . Bien que ce ne soit peut-être pas le défi le plus intéressant, en particulier pour les langues "habituelles", il peut être non trivial dans de nombreuses langues.

Le code Rosetta répertorie les fonctionnalités par langage d'approches idiomatiques du test de primalité, l'une utilisant spécifiquement le test de Miller-Rabin et l'autre utilisant la division d'essai . Cependant, "plus idiomatique" ne coïncide souvent pas avec "plus court". Dans le but de faire de Programming Puzzles et de Code Golf le site de référence pour le code golf, ce défi a pour objectif de compiler un catalogue de l’approche la plus courte dans chaque langue, similaire à "Hello, World!". et Golf vous un quine pour un grand bien! .

En outre, la possibilité de mettre en œuvre un test de primalité fait partie de notre définition du langage de programmation . Ce défi servira également de répertoire pour les langages de programmation éprouvés.

Tâche

Ecrivez un programme complet qui, avec un entier strictement positif n en entrée, détermine si n est premier et affiche une valeur de vérité ou de fausseté en conséquence.

Pour les besoins de ce défi, un entier est premier s'il a exactement deux diviseurs strictement positifs. Notez que cela exclut 1 , qui est son seul diviseur strictement positif.

Votre algorithme doit être déterministe (c'est-à-dire produire la sortie correcte avec la probabilité 1) et devrait, en théorie, fonctionner pour des entiers arbitrairement grands. En pratique, vous pouvez supposer que l’entrée peut être stockée dans votre type de données, à condition que le programme fonctionne pour les entiers de 1 à 255.

Contribution

  • Si votre langue est capable de lire à partir de STDIN, d’accepter des arguments de ligne de commande ou toute autre forme de saisie utilisateur, vous pouvez lire le nombre entier sous forme de représentation décimale, de représentation unaire (avec un caractère de votre choix), de tableau d’octets (gros ou little endian) ou simple octet (s'il s'agit du type de données le plus volumineux de votre langue).

  • Si (et seulement si) votre langue ne peut accepter aucun type de saisie utilisateur, vous pouvez coder la saisie dans votre programme.

    Dans ce cas, le nombre entier codé en dur doit être facilement échangeable. En particulier, il peut apparaître uniquement à un seul endroit dans l’ensemble du programme.

    À des fins de notation, soumettez le programme correspondant à l'entrée 1 .

Sortie

La sortie doit être écrite dans STDOUT ou l'alternative la plus proche.

Si possible, la sortie doit uniquement consister en une valeur de vérité ou de fausseté (ou une représentation de chaîne de celle-ci), suivie éventuellement d'une nouvelle ligne.

La seule exception à cette règle est la sortie constante de l'interpréteur de votre langue qui ne peut pas être supprimée, telle qu'un message d'accueil, des codes de couleur ANSI ou une indentation.

Règles supplémentaires

  • Il ne s'agit pas de trouver la langue avec l'approche la plus courte pour les tests principaux, il s'agit de trouver l'approche la plus courte dans toutes les langues. Par conséquent, aucune réponse ne sera marquée comme acceptée.

  • Les soumissions dans la plupart des langues seront notées en octets selon un codage préexistant approprié, généralement (mais pas nécessairement) UTF-8.

    La langue Piet , par exemple, sera notée en codel, ce qui est le choix naturel pour cette langue.

    Certaines langues, comme les dossiers , sont un peu difficiles à noter. En cas de doute, demandez s'il vous plaît sur Meta .

  • Contrairement à nos règles habituelles, n'hésitez pas à utiliser une langue (ou une version linguistique) même si c'est plus récent que ce défi. Si quelqu'un veut en abuser en créant un langage dans lequel le programme vide effectue un test de primalité, félicitons-le d'avoir ouvert la voie à une réponse très ennuyeuse.

    Notez qu'il doit y avoir un interprète pour que la soumission puisse être testée. Il est permis (et même encouragé) d’écrire cet interprète vous-même pour une langue non encore implémentée.

  • Si votre langue de choix est une variante triviale d'une autre langue (potentiellement plus populaire) qui possède déjà une réponse (pensez aux dialectes BASIC ou SQL, aux shells Unix ou aux dérivés triviaux de Brainfuck tels que Headsecks ou Unary), pensez à ajouter une note à la réponse existante: la même solution ou une solution très similaire est également la plus courte dans l’autre langue.

  • Les fonctions intégrées permettant de tester la primalité sont autorisées. Ce défi a pour but de cataloguer la solution la plus courte possible dans chaque langue. Par conséquent, s'il est plus court d'utiliser un langage intégré dans votre langue, foncez.

  • Sauf si elles ont été annulées précédemment, toutes les règles standard code-golf s'appliquent, y compris le http://meta.codegolf.stackexchange.com/q/1061 .

En passant, veuillez ne pas annuler les réponses ennuyeuses (mais valables) dans des langues où il n’ya pas grand chose à jouer au golf; ceux-ci sont toujours utiles à cette question car elle tente de compiler un catalogue aussi complet que possible. Cependant, faites principalement des réponses upvote dans les langues où l’auteur devait réellement s’efforcer de jouer au code.

Catalogue

L'extrait de pile au bas de cet article génère le catalogue à partir des réponses a) sous forme de liste des solutions les plus courtes par langue et b) sous forme de classement global.

Pour vous assurer que votre réponse apparaît, commencez votre réponse par un titre, en utilisant le modèle Markdown suivant:

## Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores en les effaçant. Par exemple:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Si vous souhaitez inclure plusieurs numéros dans votre en-tête (par exemple, parce que votre score est la somme de deux fichiers ou si vous souhaitez répertorier séparément les pénalités d'indicateur d'interprétation), assurez-vous que le score réel est le dernier numéro de l'en-tête:

## Perl, 43 + 2 (-p flag) = 45 bytes

Vous pouvez également faire du nom de la langue un lien qui apparaîtra ensuite dans l'extrait de code:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Afficher l'extrait de code

code-golf number number-theory primes decision-problem Dennis
la source
Puis-je prendre les entrées sous forme de nombres négatifs, où abs (entrée) serait le nombre que je teste?
Stan Strum
Non, l'entrée est un entier strictement positif.
Dennis
1
@ LyndonWhite Ceci était conçu comme un catalogue (comme «Hello, World!» ) De tests de primalité, donc un format de soumission unifié semblait préférable. C’est l’une des deux décisions que je regrette à propos de ce défi, l’autre n’autorisant que des tests de primalité déterministes.
Dennis
1
@Shaggy On dirait une question de méta.
Dennis
1
Oui, c'est ce que je pensais. Je vous laisse faire les honneurs, vu que c'est votre défi.
Shaggy

Réponses:

226

Bonjour le monde! , 13

hello, world!
histocrate
la source
83
Avez-vous simplement créé ce langage, uniquement pour cette soumission? ;)
ETHproductions
41
@ETHproductions On dirait que le dernier commit date de 10 jours.
Geobits
39
J'espérais avoir un langage un peu plus en forme avant de le lier n'importe où, mais ce défi a été posté et je n'ai pas pu résister.
Histocrat
31
Je dirais presque que suspendre à une entrée de 1 correspond à une fonctionnalité correcte.
iamnotmaynard le
22
La meilleure partie de ceci est que le programme n'est pas simplement intégré, chaque personnage joue son propre rôle pour obtenir le résultat correct.
ETHproductions
157

Hexagonie , 29 octets

.?'.).@@/'/.!.>+=(<.!)}($>(<%

La version lisible de ce code est:

   . ? ' .
  ) . @ @ /
 ' / . ! . >
+ = ( < . ! )
 } ( $ > ( <
  % . . . .
   . . . .

Explication: Il vérifie s'il existe un nombre compris entre 2 et n-1 qui divise n.

Initialisation:

Écrivez n dans une cellule de mémoire et n-1 dans une autre:

   . ? ' .
  . . . . .
 . . . . . .
+ = ( . . . .
 . . . . . .
  . . . . .
   . . . .

Cas spécial n = 1:

Imprimer un 0 et terminer

   . . . .
  . . . @ .
 . . . ! . .
. . . < . . .
 . . . . . .
  . . . . .
   . . . .

La boucle

Calculez n% a et diminuez a. Terminez si a = 1 ou n% a = 0.

   . . . .
  ) . . . /
 ' / . . . >
. . . . . . .
 } ( $ > ( <
  % . . . .
   . . . .

Cas a = 1:

Augmentez un 0 à un 1, imprimez-le et terminez. (Le pointeur d'instruction tourne dans la direction NE et fait une boucle du coin est au coin sud-ouest. Et le $ s'assure qu'il ignore la commande suivante)

   . . . .
  . . . @ .
 . . . ! . .
. . . < . . )
 . . $ . . <
  . . . . .
   . . . .

Cas a% n = 0:

Imprime le 0 et termine (Le pointeur d’instruction est en cours d’exécution et tourne en boucle vers le @

   . . . .
  . . @ . .
 . . . . . >
. . . . . ! .
 . . . . . .
  . . . . .
   . . . .
Etoplay
la source
61
Bon sang, c'est un premier post impressionnant. :) Je vais mettre la prime à l'heure actuelle (je l'attribuerai dans 7 jours pour attirer davantage l'attention sur votre réponse). Bienvenue chez PPCG!
Martin Ender
35
Très bonne réponse! +1 pour " La version lisible de ce code est: <...> " :-)
agtoever
68

Hexagony , 218 92 58 55 octets

Avis: Cette réponse a été solidement battue avec une solution de côté 4 par Etoplay.

)}?}.=(..]=}='.}.}~./%*..&.=&{.<......=|>(<..}!=...&@\[

Le tout premier programme Hexagony non-trivial (c'est-à-dire non linéaire)! Elle repose sur la même approche factorielle au carré que la réponse Labyrinth de Sp3000 . Après avoir démarré avec un hexagone de taille 10, j'ai réussi à le comprimer à la taille 5. Cependant, je suis en mesure de réutiliser un code en double et il y a encore tout à fait un tas de pas d'habitation dans le code, donc la taille 4 pourrait juste être possible.

Explication

Pour donner un sens au code, nous devons d’abord le déplier. Hexagony ajoute n'importe quel code source au nombre hexagonal centré suivant avec no-ops ( .), ce qui est 61. Il réorganise ensuite le code en un hexagone régulier de la taille correspondante:

     ) } ? } .
    = ( . . ] =
   } = ' . } . }
  ~ . / % * . . &
 . = & { . < . . .
  . . . = | > ( <
   . . } ! = . .
    . & @ \ [ .
     . . . . .

Ceci est assez lourdement joué avec des chemins d'exécution qui se chevauchent et se chevauchent et de multiples pointeurs d'instruction (IP). Pour expliquer son fonctionnement, examinons tout d'abord une version non-golfée où le flux de contrôle ne passe pas par les bords, une seule adresse IP est utilisée et les chemins d'exécution sont aussi simples que possible:

             . . . . . . . . . . . . .
            . . . . . . . . . . . . . .
           . . . . . . . . . . . . . . .
          . . . . . . . . . . @ . . . . .
         . . . . . . . . . . ! . . . . . .
        . . . . . . . . . . % . . . . . . .
       . . . . . . . . . . ' . . . . . . . .
      . . . . . . . . . . & . . . . . . . . .
     . . . . . . . . . . { . . . . . . . . . .
    . . . . . . . . . . * . . . . . . . . . . .
   . . . . . . . . . . = . . . . . . . . . . . .
  . . . . . . . . . . } . . . . . . . . . . . . .
 ) } ? } = & { < . . & . . . . . . . . . . . . . .
  . . . . . . . > ( < . . . . . . . . . . . . . .
   . . . . . . = . . } . . . . . . . . . . . . .
    . . . . . } . . . = . . . . . . . . . . . .
     . . . . | . . . . | . . . . . . . . . . .
      . . . . * . . . ) . . . . . . . . . . .
       . . . . = . . & . . . . . . . . . . .
        . . . . > } < . . . . . . . . . . .
         . . . . . . . . . . . . . . . . .
          . . . . . . . . . . . . . . . .
           . . . . . . . . . . . . . . .
            . . . . . . . . . . . . . .
             . . . . . . . . . . . . .

Note latérale: le code ci-dessus commence par l'exécution de la première ligne, qui est pleine de no-ops. Ensuite, lorsque l'adresse IP atteint le bord nord-est, elle se termine au coin le plus à gauche (le )), où le code commence.

Avant de commencer, un mot sur la structure de la mémoire de Hexagony. C'est un peu comme la bande de Brainfuck sur des stéroïdes. En fait, ce n'est pas une bande, mais une grille hexagonale elle-même (une infinie), où chaque arête a une valeur entière, qui est initialement 0 (et contrairement au standard Brainfuck, les valeurs sont des entiers signés de précision arbitraire). Pour ce programme, nous utiliserons quatre arêtes:

entrez la description de l'image ici

Nous allons calculer le factoriel sur le bord A , décompter notre entrée sur le bord C et stocker une autre copie de l'entrée (pour le modulo) sur le bord D . B est utilisé comme une arête temporaire pour les calculs.

Le pointeur de mémoire (MP) commence sur le bord A et pointe vers le nord (ce qui est important pour déplacer le MP). Maintenant, voici le premier bit du code:

)}?}=&{

)incrémente bord A pour 1que la base de la factorielle. }oblige le député à tourner à droite, c’est-à-dire à se diriger vers l’arête C (en direction nord-est). Ici, nous lisons l’entrée sous forme d’entier avec ?. Ensuite, nous prenons un autre virage à droite vers D avec }. =inverse le MP, de telle sorte qu'il pointe sur le sommet partagé avec C . &copie la valeur de C (entrée) dans D - la valeur est copiée de gauche car la valeur actuelle est non positive (zéro). Enfin, nous faisons tourner le député à gauche en C avec {.

Ensuite, <techniquement , il s’agit d’une branche, mais nous savons que la valeur actuelle est positive, l’IP tournera toujours à droite vers le >. Une branche frappé par les actes secondaires comme un miroir, de telle sorte que l'IP se déplace horizontalement à nouveau, vers la (, qui décrémente la valeur de C .

La branche suivante <est en fait une branche maintenant. Voici comment on boucle de n-1bas en haut 1. Alors que la valeur actuelle de C est positive, l’IP tourne à droite (pour exécuter la boucle). Une fois que nous atteignons zéro, il tournera à gauche.

Regardons la boucle "corps". Ce |sont de simples miroirs, >et <sont également utilisés à nouveau. Cela signifie que le corps de la boucle se résume à

}=)&}=*}=

}déplace le PM vers l’arête B , =inverse sa direction pour faire face au sommet ABC . )incrémente la valeur: cela ne concerne que la première itération, où la valeur de B est toujours égale à zéro: nous voulons nous assurer qu'elle est positive, de sorte que l'instruction suivante &copie le voisin de droite , c'est-à-dire A , c'est-à-dire la valeur actuelle de la factorielle. calcul, en B .

}déplace ensuite le PM vers A , l’ =inverse à nouveau pour faire face au sommet commun. *multiplie les deux voisins, à savoir les bords B et C et stocke le résultat dans A . Enfin, nous en avons un autre }=à retourner en C , toujours face au sommet ABC .

J'espère que vous pouvez voir comment cela calcule le factoriel n-1en A .

Alors maintenant que nous avons fait cela, le compteur de boucles en C est zéro. Nous voulons carréer la factorielle et ensuite prendre le modulo avec l'entrée. C'est ce que fait ce code:

&}=*{&'%!@

Puisque C est égal à zéro, &copie le voisin de gauche, à savoir le factoriel A . }=*se déplace vers B et stocke le produit des deux copies de la factorielle ( à savoir le carré) en B . {revient en C , mais n'inverse pas le député. Nous savons que la valeur actuelle est maintenant positif, donc &entrée des copies de D en C . 'la MP en arrière vers la droite, soit sur A . Rappelez - vous, le carré de la factorielle est en B et l'entrée est en C . Donc, %calcule (n-1)!^2 % nexactement ce que nous recherchons.!affiche le résultat sous forme d’entier (0 ou 1) et @termine le programme.

D'accord, mais c'était la version sans golf. Qu'en est-il de la version golfée? Vous devez savoir deux choses supplémentaires sur Hexagony:

  1. Les bords s'enroulent. Si l'IP frappe un bord de l'hexagone, il saute au bord opposé. Ceci est ambigu lorsque l’IP frappe un coin droit, c’est-à-dire qu’il agit également comme une branche: si la valeur actuelle est positive, l’IP saute vers le bord de la grille à sa droite, sinon vers celle à sa gauche.
  2. Il y a actuellement 6 IPs. Chacun d'entre eux commence dans un coin différent, se déplaçant le long du bord dans le sens des aiguilles d'une montre. Un seul d'entre eux est actif à la fois, ce qui signifie que vous pouvez simplement ignorer les 5 autres adresses IP si vous n'en voulez pas. Vous pouvez passer à l'adresse IP suivante (dans le sens des aiguilles d'une montre) avec ]et à l' adresse précédente avec [. (Vous pouvez aussi en choisir un spécifique #, mais pour une autre fois.)

Il contient également quelques nouvelles commandes: \et /sont des miroirs semblables à |, et ~multiplient la valeur actuelle par -1.

Alors, comment la version non-golfée se traduit-elle par la version golfée? Le code de configuration linéaire )}?}=&{et la structure de boucle de base peuvent être trouvés ici:

        ) } ? } .  ->
       . . . . . .
      . . . . . . .
     . . . . . . . .
->  . = & { . < . . .
     . . . . . > ( <
      . . . . . . .
       . . . . . .
        . . . . .

Maintenant, le corps de la boucle traverse les bords plusieurs fois, mais surtout, le calcul réel est transféré à l'IP précédente (qui commence dans le coin gauche en direction du nord-est):

        ) . . . .
       = . . . ] .
      } = . . } . .
     ~ . / . * . . .
    . . . . . . . . .
     . . . = . > ( <
      . . } . = . .
       . & . \ [ .
        . . . . .

Après avoir rebondi sur la branche en direction du sud-est, l’IP s’enroule du bord aux deux =angles situés dans le coin supérieur gauche (qui, ensemble, ne font pas exception), puis rebondit sur le /. Le ~intervertit le signe de la valeur actuelle, ce qui est important pour les itérations suivantes. La propriété intellectuelle tourne à nouveau autour du même bord et frappe finalement [où le contrôle est transféré à l'autre adresse IP.

Celui-ci exécute maintenant ~}=)&}=*}ce qui annule la négation, puis exécute simplement le corps de la boucle non-golfée (moins le =). Enfin, il convient ]que les mains contrôlent l’adresse IP d'origine. (Notez que la prochaine fois que nous exécuterons cette adresse IP, elle commencera à l'endroit où elle s'était arrêtée, elle se mettra donc au coin. Nous avons besoin que la valeur actuelle soit négative pour que l'adresse IP revienne au bord nord-ouest au lieu de celle du sud-est.)

Une fois que l'IP d'origine reprend le contrôle, elle rebondit sur \, exécute le reste =, puis clique >pour alimenter l'itération de boucle suivante.

Maintenant la partie la plus folle: que se passe-t-il quand la boucle se termine?

        ) . . . .
       . ( . . ] =
      . . ' . } . }
     . . . % * . . &
    . . . . . . . . .
     . . . = | . . <
      . . } ! . . .
       . & @ . . .
        . . . . .

La propriété intellectuelle se déplace vers le nord-est de la <et englobe la diagonale nord-est. Donc, il se termine sur le même chemin d’exécution que le corps de la boucle ( &}=*}]). Ce qui est en fait plutôt cool, car c’est exactement le code que nous voulons exécuter à ce stade, du moins si nous en ajoutons un autre =}(car }=}c’est équivalent à {). Mais comment cela ne rentre-t-il pas réellement dans la boucle précédente? Car ]passe à la prochaine adresse IP qui est maintenant l’IP (jusqu’à présent inutilisée) qui commence dans le coin supérieur droit, en direction du sud-ouest. À partir de là, l’IP continue le long du bord, s’enroule dans le coin supérieur gauche, descend de la diagonale, rebondit |et termine au @tout en exécutant le dernier bit de code linéaire:

=}&)('%!@

(Le )(n'est pas une opération, bien sûr - je devais ajouter le (parce que le )était déjà là.)

Ouf ... quel gâchis ...

Martin Ender
la source
Agréable! Comment est-ce nouveau? Aussi, vous voudrez peut-être créer une page esolangs chaque fois que vous aurez une version stable
mbomb007
18
@ mbomb007 J'ai implémenté le langage il y a deux jours (et je l'ai conçu plus de deux ou trois jours auparavant). Et oui, je vais certainement ajouter une page esolangs, mais je pense que la spécification n'est pas encore stable à 100% (il y a encore 3 commandes non attribuées par exemple). Une fois que j’ai le sentiment que c’est plus stable, je l’ajouterai à nos deux esolangs et à notre méta-post.
Martin Ender
Sous l'hexagone élargi se trouve le coin le plus à gauche (le 1) . De quoi 1parles-tu là?
mbomb007
@ mbomb007 corrigé. L' )habitude d'être un 1.
Martin Ender
5
+1 uniquement pour le niveau de détail de votre explication. Si plus de langues venaient avec un exemple détaillé, plus de gens pourraient les utiliser: D
jdarling
66

Pyth, 4 octets

}QPQ

Impressions Trueou False.

orlp
la source
12
Je sais que c'est vieux, mais maintenant vous pouvez aussi le faire comme ceci: P_Q et sauvegarder 1 octet.
drobilc
14
C'est maintenant possible avecP_
Blue
3
@drobilc Vous pouvez couper le Q, en tant qu'EOF lorsque la fonction attend un argument, elle utilise l'entrée
Stan Strum
55

Retina , 16 octets

^(?!(..+)\1+$)..

Essayez-le en ligne!

Commençons par un classique: détecter les nombres premiers avec une expression rationnelle . La saisie doit être unaire , en utilisant tout caractère imprimable répété. La suite de tests inclut une conversion de décimale en unaire pour plus de commodité.

Un programme Retina composé d'une seule ligne traite cette ligne comme une expression rationnelle et affiche le nombre de correspondances trouvées dans l'entrée, ce qui correspond 0aux nombres composés et 1aux nombres premiers.

Le lookahead garantit que l'entrée n'est pas composite: le retour arrière essaie toutes les sous-chaînes possibles (d'au moins 2 caractères), car (..+)le lookahead tente ensuite de faire correspondre le reste de l'entrée en répétant ce qui a été capturé ici. Si cela est possible, cela signifie que l’entrée a un diviseur supérieur à 1, mais inférieur à lui-même. Si tel est le cas, la prévision négative entraîne l'échec de la correspondance. Pour les nombres premiers, cette possibilité n'existe pas, et le match continue.

Le seul problème est que ce lookahead accepte également 1, nous l' excluons donc en faisant correspondre au moins deux caractères ...

Martin Ender
la source
C'est en fait une expression irrégulière, car les nombres premiers ne forment pas un langage régulier.
PyRulez
@PyRulez La plupart des saveurs de regex du monde réel sont beaucoup plus puissantes que le concept théorique d'expressions régulières. J'ai amélioré la formulation cependant.
Martin Ender
1
Les moteurs de "regex" les plus puissants actuellement en vente libre ont maintenant un pouvoir de reconnaissance égal à celui d'un automate lié linéaire. Les expressions rationnelles, les récursions de motifs, les requêtes illimitées et les recherches illimitées sont tout ce dont vous avez besoin pour une analyse contextuelle (bien que les références arrière et une telle aide généralement à compliquer une analyse efficace), et certaines les ont toutes. Ne me lancez même pas sur les moteurs qui vous permettent d'intégrer du code dans la regex.
eaglgenes101
52

CJam, 4 octets

qimp

CJam a un opérateur intégré pour les tests de primalité.

Peter Taylor
la source
18
Alternativement:limp
Sp3000 le
43
pimpmon cjam.
flawr
12
pimpest objectivement plus proxénète
MickLH
1
Vous pouvez également fairel~mp
vaches charlatan
12
@Cyoce, qlit une ligne d’entrée, l’ ianalyse comme un entier et mpl’ intègre . CJam a deux groupes de caractères intégrés à deux caractères: les "étendus" commencent eet les "mathématiques" commencentm
Peter Taylor
48

HTML + CSS, 254 + n max * 28 octets

Nous pouvons vérifier la primalité à l'aide d'expressions régulières. Mozilla a @document, qui est défini comme:

@document [ <url> | url-prefix(<string>) | domain(<string>) | regexp(<string>) ]# {
  <group-rule-body>
}

Pour filtrer des éléments via CSS en fonction de l'URL actuelle. Ceci est un seul passage, nous devons donc faire deux étapes:

  1. Obtenez les commentaires de l'utilisateur. Cette entrée doit en quelque sorte être reflétée dans l'URL actuelle.
  2. Répondez à l'utilisateur avec le moins de code possible.

1. Obtenir une entrée

Le moyen le plus rapide que je puisse comprendre pour obtenir une entrée et le transférer à l'URL est un GETformulaire avec des cases à cocher. Pour la regex, nous avons juste besoin d'une chaîne unique pour compter les apparences.

Nous commençons donc par ceci (61 octets):

<div id=q><p id=r>1<p id=s>0</div><form method=GET action=#q>

Nous avons deux <p>s uniques pour indiquer si le nombre entré est un nombre premier (1) ou non (0). Nous définissons également la forme et son action.

Suivi par n max cases portant le même nom (n max * 28 octets):

<input type=checkbox name=i>

Suivi de l'élément submit (34 octets):

<input name=d value=d type=submit>

2. Afficher la réponse

Nous avons besoin du CSS (159 octets) pour sélectionner l’ <p>affichage (1 ou 0):

#q,#s,#q:target{display:none}#q:target{display:block}@-moz-document regexp(".*\\?((i=on&)?|(((i=on&)(i=on&)+?)\\4+))d=d#q$"){#s{display:block}#r{display:none}}

»Essayez-le sur codepen.io (firefox uniquement)

mınxomaτ
la source
12
+1: Ceci est mon abus favori de tous les temps avec HTML, et le genre de choses qui me font aimer CodeGolf.
Chat
C'est certes intéressant, mais je ne suis pas sûr que cela réponde aux règles de ce défi. En particulier, je ne pense pas qu'il soit conforme à votre algorithme [...] devrait, en théorie, fonctionner pour des entiers arbitrairement grands. Ne pourriez-vous pas utiliser une expression rationnelle sur la valeur d'un champ de saisie également?
Dennis
@ Dennis Peut-être. Probablement même. Mais cela ne résoudrait pas le problème que vous avez mentionné. Je le laisse ici comme une entrée non-concurrentielle, parce que c'est le défi le plus d'actualité pour cela.
mınxomaτ
Pourquoi pas? Si vous avez un nombre en unaire dans un champ de saisie, votre code ne dépendra plus du nombre maximum.
Dennis
5
Hm, j'ai pensé à cela un peu plus, et il n'y a vraiment aucune différence entre avoir seulement x cases à cocher et un interpréteur qui n'a que des nombres de y bits. Ignorer mon commentaire précédent.
Dennis
45

Aidez-moi, WarDoq! , 1 octet

P

Sorties 1 si l'entrée est principale, 0 sinon.

orlp
la source
40

Hexagonie , 28 octets

Étant donné qu'Etoplay m'a absolument critiqué sur cette question , j'ai senti que je devais jouer au golf, sa seule autre réponse .

?\.">"!*+{&'=<\%(><.*.'(@>'/

Essayez-le en ligne!

J'utilise le théorème de Wilson, comme l'a fait Martin dans sa réponse : Donné n, je sortie(n-1!)² mod n

Voici le programme dévoilé:

   ? \ . "
  > " ! * +
 { & ' = < \
% ( > < . * .
 ' ( @ > ' /
  . . . . .
   . . . .

Et voici la version lisible :

Très lisible

Explication:

Le programme comporte trois étapes principales: initialisation , factorielle et sortie .

Le modèle de mémoire d'Hexagony est une grille hexagonale infinie. J'utilise 5 emplacements de mémoire, comme indiqué dans ce diagramme:

Mémoire

Je ferai référence à ces emplacements (et aux entiers qui y sont stockés) par leurs étiquettes sur ce diagramme.

Initialisation:

Initialisation

Le pointeur d'instruction ( IP ) commence dans le coin supérieur gauche, en direction est. Le pointeur de mémoire ( MP ) commence à IN .

Tout d'abord, ?lit le numéro de l'entrée et le stocke dans IN . L' IP reste sur le chemin bleu, reflété par \. La séquence "&(déplace le MP vers la gauche (vers A ), copie la valeur de IN vers A et la décrémente.

L’ IP quitte alors un côté de l’hexagone et rentre de l’autre côté (sur le chemin vert). Il exécute '+qui déplace le MP à B et des copies ce qui était en A . <redirige l' IP vers l'ouest.

Factorielle:

Je calcule la factorielle d'une manière spécifique, de sorte que sa quadrature est facile. Je stocke n-1!dans B et C comme suit.

Factorielle

Le pointeur d'instruction commence sur le chemin bleu, en direction de l'est.

='inverse le sens de la MP et le déplace vers l' arrière à C . Cela équivaut à, {=mais avoir la =où il était était utile plus tard.

&{copie la valeur de A à C , puis déplace le MP retour à un . L’ IP suit ensuite le chemin vert, ne faisant rien, avant d’atteindre le chemin rouge, de frapper \et d’aller sur le chemin orange.

Avec (>, nous décrémentons A et redirigeons l’ IP Est. Ici , il frappe une branche: <. Pour le positif A , nous continuons sur le chemin orange. Sinon, la propriété intellectuelle est dirigée vers le nord-est.

'*déplace le MP pour B et stocke A * C dans B . C’est (n-1)*(n-2)là que l’entrée initiale était n. L' IP rentre ensuite dans la boucle initiale et continue à décrémenter et à se multiplier jusqu'à ce que A atteigne 0. (informatique n-1!)

NB : Sur les boucles suivantes, &stocke la valeur de B dans C , C ayant maintenant une valeur positive. Ceci est crucial pour le calcul factoriel.

Sortie:

Sortie

Quand A atteint 0. La branche dirige l’ IP le long du chemin bleu.

=*inverse la MP et stocke la valeur de B * C dans A . Ensuite, l’ IP sort de l’hexagone et rentre sur le chemin vert; l'exécution "%. Ceci déplace le MP vers OUT et calcule A mod IN , ou (n-1!)² mod n.

Ce qui suit {"agit comme un no-op, car ils s'annulent. !imprime la sortie finale et *+'(sont exécutés avant la fin: @.

Après exécution, (avec une entrée de 5) la mémoire ressemble à ceci:

Mémoire2

Les superbes images du flux de contrôle ont été réalisées avec Hexagony Coloror de Timwi .

Merci à Martin Ender pour avoir généré toutes les images, je ne pouvais pas le faire sur mon PC.

H.PWiz
la source
Qu'utilisez-vous pour ces diagrammes de mémoire? J'ai vu IDE ésotérique, mais je ne pouvais pas le faire fonctionner ...
NieDzejkob
@NieDzejkob, vous feriez mieux de demander à Martin de discuter, car il les a tout de même faites pour moi.
H.PWiz
@NieDzejkob Ouais, le diagramme de mémoire peut être exporté depuis EsoIDE. chat.stackexchange.com/rooms/27364/… si vous voulez en discuter un peu plus.
Martin Ender
34

Croissant Mornington , 2448 octets

Nous sommes de retour à Londres!

Take Northern Line to Bank
Take Circle Line to Bank
Take District Line to Parsons Green
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upney
Take District Line to Hammersmith
Take Circle Line to Victoria
Take Victoria Line to Seven Sisters
Take Victoria Line to Victoria
Take Circle Line to Victoria
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take Circle Line to Cannon Street
Take Circle Line to Hammersmith
Take Circle Line to Cannon Street
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Hammersmith
Take Circle Line to Notting Hill Gate
Take Circle Line to Hammersmith
Take Circle Line to Notting Hill Gate
Take District Line to Upminster
Take District Line to Bank
Take Circle Line to Victoria
Take Circle Line to Temple
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Pinner
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Victoria
Take Circle Line to Aldgate
Take Circle Line to Victoria
Take Circle Line to Victoria
Take District Line to Upminster
Take District Line to Embankment
Take Circle Line to Embankment
Take Northern Line to Angel
Take Northern Line to Moorgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Aldgate
Take Circle Line to Cannon Street
Take District Line to Upney
Take District Line to Cannon Street
Take District Line to Acton Town
Take District Line to Acton Town
Take Piccadilly Line to Russell Square
Take Piccadilly Line to Hammersmith
Take Piccadilly Line to Russell Square
Take Piccadilly Line to Ruislip
Take Piccadilly Line to Ruislip
Take Metropolitan Line to Preston Road
Take Metropolitan Line to Aldgate
Take Circle Line to Aldgate
Take Circle Line to Cannon Street
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Preston Road
Take Metropolitan Line to Moorgate
Take Circle Line to Moorgate
Take Northern Line to Mornington Crescent

Timwi a eu la gentillesse d'implémenter les stations de contrôle de flux Templeet Angeldans l' ESE Esoteric , ainsi que d'ajouter une analyse des entrées et des entiers à la spécification du langage.

Celui-ci est probablement mieux joué que le "Hello, World!", Car cette fois-ci, j'ai écrit un script CJam pour m'aider à trouver le chemin le plus court entre deux stations. Si vous voulez l'utiliser (bien que je ne sache pas pourquoi quelqu'un voudrait ...), vous pouvez utiliser l'interprète en ligne . Collez ce code:

"Mornington Crescent"
"Cannon Street"
]qN/{'[/0=,}$:Q;{Q{1$#!}=\;_oNo'[/1>{']/0="[]"\*}%}%:R;NoQ{R\f{f{\#)}:+}:*},N*

Ici, les deux premières lignes sont les stations que vous voulez vérifier. Collez également le contenu de cette boîte à copier dans la fenêtre de saisie.

La sortie vous montrera quelles lignes sont disponibles aux deux stations, puis une liste de toutes les stations qui relient les deux, triées en fonction de la longueur du nom des stations. Elle les montre toutes, car il est parfois préférable d’utiliser un nom plus long, soit parce qu’elle permet une ligne plus courte, soit parce que la station est spéciale (comme Bank ou Temple) afin que vous souhaitiez l’éviter. Il existe des cas extrêmes où deux stations ne sont pas connectées par une seule et même station (notamment, les lignes Metropolitan et District ne se croisent jamais), auquel cas vous devez trouver autre chose. ;)

Le code MC, quant à lui, est basé sur l’approche factorielle au carré, comme beaucoup d’autres réponses, car MC a la multiplication, la division et le modulo. En outre, j'ai pensé qu'une seule boucle serait pratique.

Un problème est que les boucles sont des boucles do-while, et que la décrémentation et l’incrémentation sont chères, je ne peux donc pas facilement calculer (n-1)!(pour n > 0). Au lieu de cela, je calcule n!puis divise parn la fin. Je suis sûr qu'il existe une meilleure solution pour cela.

Quand j'ai commencé à écrire cela, je pensais que stocker -1à Hammersmith serait une bonne idée pour pouvoir décrémenter à moindre coût, mais au final, cela aurait pu coûter plus cher que d'économiser. Si je trouve la patience de le refaire, je pourrais peut-être essayer de me contenter de rester -1à Upminster pour pouvoir utiliser Hammersmith à des fins plus utiles.

Martin Ender
la source
10
Londres est-il complet?
Rohan Jhunjhunwala
1
@RohanJhunjhunwala probablement
Martin Ender
Hou la la! J'aime voir des questions bien pensées. J'aime particulièrement voir des questions où vous devez écrire un programme pour écrire un programme.
Rohan Jhunjhunwala
27

Brachylog (V2), 1 octet

ṗ

Essayez-le en ligne!

Brachylog (V1), 2 octets

#p

Ceci utilise le prédicat intégré #p - Prime , ce qui contraint son entrée à être un nombre premier.

Brachylog est ma tentative de créer une version Code Golf de Prolog, un langage déclaratif de golf qui utilise le retour en arrière et l’unification.

Solution alternative non intégrée: 14 octets

ybbrb'(e:?r%0)

Voici le détail du code ci-dessus:

y            The list [0, …, Input]
bbrb         The list [2, …, Input - 1]
'(           True if what's in the parentheses cannot be proven; else false
     e           Take an element from the list [2, …, Input - 1]
     :?r%0       The remainder of the division of the Input but that element is 0
)
Fataliser
la source
1
Vous voudrez peut-être également modifier la version de Brachylog 2 dans l'article, maintenant que la syntaxe est un octet plus court.
1
@ ais523 Vrai, c'est fait.
Fataliser
Le Brachylog 2 répond-il après le défi?
Scott Milner
1
@ScottMilner Oui, mais cela est explicitement autorisé dans ce défi: "Contrairement à nos règles habituelles, n'hésitez pas à utiliser un langage (ou une version linguistique) même s'il est plus récent que ce défi"
Fataliser
26

Haskell, 49 octets

Utilisation du corollaire de xnor dans le théorème de Wilson :

main=do n<-readLn;print$mod(product[1..n-1]^2)n>0
Lynn
la source
Ne serait-il pas plus court main=interact$\n-> ...?
John Dvorak
2
Contre-intuitivement, non! Considérez que vous auriez besoin interact...readde quelque part, ce qui le rend beaucoup plus long que juste readLn. La donotation peut souvent être plus concise que ce à quoi vous pouvez vous attendre, surtout lorsque l’alternative est un lambda.
Lynn
24

Labyrinthe , 29 octets

1
?
:
}  +{%!@
(:'(
 } {
 :**

Lit un entier de STDIN et les sorties ((n-1)!)^2 mod n. Théorème de Wilson est très utile pour ce défi.

Le programme commence dans le coin supérieur gauche, en commençant par 1lequel multiplie le haut de la pile par 10 et en ajoute 1. C’est la façon dont Labyrinth construit de grands nombres, mais comme les piles de Labyrinthe sont remplies de zéros, l’effet final juste poussé un 1.

?puis lit à npartir de STDIN et le :duplique. }passe nà la pile auxiliaire, à utiliser à la fin du modulo. (puis décrémente n, et nous sommes prêts à commencer à calculer le factoriel au carré.

Notre deuxième :(duplicata) est à une jonction, et c'est ici que les fonctionnalités de contrôle du flux de Labyrinth entrent en jeu. À une jonction après l'exécution d'une instruction, si le sommet de la pile est positif, nous tournons à droite, pour le négatif, nous tournons à gauche et pour le zéro, nous continuons tout droit. Si vous essayez de vous retourner mais que vous frappez un mur, Labyrinth vous fait plutôt tourner dans l'autre sens.

Car n = 1, puisque le haut de la pile est ndécrémenté, ou 0nous allons tout droit. Nous avons ensuite frappé un no-op 'suivi par un autre décrément (qui nous met à -1. C'est négatif, alors nous tournons à gauche, en exécutant +plus ( -1 + 0 = -1), {pour nrevenir en arrière de la pile auxiliaire à la main et à %modulo ( -1 % 1 = 0). Puis on sort avec !et on termine avec @.

Au n > 1deuxième :tour on tourne à droite. Nous décalons ensuite }notre compteur de boucle copié vers la pile auxiliaire, dupliquons :et multiplions deux fois **, avant de décaler le compteur {et de le décrémenter (. Si nous sommes toujours positifs, nous essayons de tourner à droite mais nous ne pouvons pas, alors Labyrinth nous fait plutôt tourner à gauche, continuant ainsi la boucle. Sinon, le sommet de la pile est notre compteur de boucles qui a été réduit à 0 et que nous +ajoutons à notre calcul ((n-1)!)^2. Enfin, nous nrevenons en arrière avec {modulo %, output !et terminate @.

J'ai dit que 'c'est un non-op, mais il peut également être utilisé pour le débogage. Courez avec le -ddrapeau pour voir l’état de la pile à chaque 'passage!

Sp3000
la source
2
Tailler la factorielle est un truc vraiment cool :)
Lynn
@Mauris Merci! J'ai besoin de donner un crédit là où c'est dû cependant - j'ai d'abord vu le truc utilisé par xnor ici
Sp3000
5
Oui, la première réponse du labyrinthe n'a pas été écrite par moi! :)
Martin Ender
24

Utilitaires Bash + GNU, 16

  • 4 octets sauvegardés grâce à @Dennis

  • 2 octets sauvés grâce à @Lekensteyn

factor|awk NF==2

L'entrée est une ligne tirée de STDIN. La sortie est une chaîne vide pour falsey et une chaîne non vide pour la vérité. Par exemple:

$ ./pr.sh <<< 1
$ ./pr.sh <<< 2
2: 2
$ ./pr.sh <<< 3
3: 3
$ ./pr.sh <<< 4
$
Trauma numérique
la source
2
Cool, a appris sur un autre coreutil. Vous pouvez supprimer deux caractères en comptant le nombre de champs:factor|awk NF==2
Lekensteyn le
@Lekensteyn - merci - pour une raison quelconque, j'ai manqué votre commentaire avant :)
Digital Trauma
J'allais publier quelque chose d'un peu similaire, seulement plus longtemps et sans AWK. Bien fait.
David Conrad
21

Java, 126 121 octets

Je suppose que nous avons besoin d'une réponse Java pour le tableau de bord ... alors voici une simple boucle de division d'essai:

class P{public static void main(String[]a){int i=2,n=Short.valueOf(a[0]);for(;i<n;)n=n%i++<1?0:n;System.out.print(n>1);}}

Comme d'habitude pour Java, l'exigence "programme complet" rend cette opération beaucoup plus grande que si elle était une fonction, principalement à cause de la mainsignature.

Sous forme développée:

class P{
    public static void main(String[]a){
        int i=2,n=Short.valueOf(a[0]);
        for(;i<n;)
            n=n%i++<1?0:n;
        System.out.print(n>1);
    }
}

Edit: Corrigé et regolfé par Peter dans les commentaires. Merci!

Géobits
la source
Buggy: il signale que 1c'est primordial. Sinon, il y aurait une économie de 4 caractères en retirant pet en disantfor(;i<n;)n=n%i++<1?0:n;System.out.print(n>0);
Peter Taylor
2
OTOH class P{public static void main(String[]a){int i=2,n=Short.valueOf(a[0]);for(;i<n;)n=n%i++<1?0:n;System.out.print(n>1);}}fonctionne
Peter Taylor
6
changer la ligne 3 en 'long i = 2, n = Long.valueOf (a [0]); `ne modifie pas la longueur, mais élargit la plage des entrées valides.
James K Polk
4
Au lieu de .valueOfvous pouvez utiliser new, comme dans new Short(a[0]), ou new Long(a[0]), ce qui est un peu plus court.
ECS
3
Vous pouvez économiser 4 octets en utilisant une interface et en abandonnant le publicmodificateur.
RamenChef
18

Brain-Flak , 112 108 octets

({}[()]){((({})())<>){{}<>(({}<(({}[()])()<>)>)<>)<>{({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}}}<>{{}}([]{})

Essayez-le en ligne!

Comment ça fonctionne

Initialement, la première pile contiendra un entier positif n , la deuxième pile sera vide.

Nous commençons par décrémenter n comme suit.

(
  {}      Pop n.
  [()]    Yield -1.
)       Push n - 1.

n = 1

Si n = 1 est égal à zéro, la boucle while

{
  ((({})())<>)
  {
    {}<>(({}<(({}[()])()<>)>)<>)<>{({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}
  }
}

est sauté entièrement. Enfin, le code restant est exécuté.

<>    Switch to the second stack (empty).
{}    Pop one of the infinite zeroes at the bottom.
{<>}  Switch stacks while the top on the active stack is non-zero. Does nothing.
(
  []    Get the length of the active stack (0).
  {}    Pop another zero.
)     Push 0 + 0 = 0.

n> 1

Si n - 1 est non nul, nous entrons dans la boucle que n = 1 saute. Ce n'est pas une "vraie" boucle; le code n'est exécuté qu'une fois. Il réalise ce qui suit.

{                   While the top of the active stack is non-zero:
  (
    (
      ({})                Pop and push n - 1.
      ()                  Yield 1.
    )                   Push n - 1 + 1 = n.
    <>                  Switch to the second stack. Yields 0.
  )                   Push n + 0 = n.
                      We now have n and k = n - 1 on the first stack, and n on
                      the second one. The setup stage is complete and we start
                      employing trial division to determine n's primality.
  {                   While the top of the second stack is non-zero:
    {}                  Pop n (first run) or the last modulus (subsequent runs),
                        leaving the second stack empty.
    <>                  Switch to the first stack.
    (
      (
        {}                  Pop n from the first stack.
        <
          (
            (
              {}              Pop k (initially n - 1) from the first stack.
              [()]            Yield -1.
            )               Push k - 1 to the first stack.
            ()              Yield 1.
            <>              Switch to the second stack.
          )               Push k - 1 + 1 = k on the second stack.
        >               Yield 0.
      )               Push n + 0 = n on the second stack.
      <>              Switch to the first stack.
    )               Push n on the first stack.
    <>              Switch to the second stack, which contains n and k.
                    The first stack contains n and k - 1, so it is ready for
                    the next iteration.
    {({}[()]<({}[()]<({}())>)>{(<()>)}{})}{}{}  Compute and push n % k.
  }               Stop if n % k = 0.
}               Ditto.

n% k est calculé à l'aide de l'algorithme de module sur 42 octets de ma réponse au test de divisibilité .

Enfin, nous interprétons les résultats pour déterminer la primalité de n .

<>    Switch to the first stack, which contains n and k - 1, where k is the
      largest integer that is smaller than n and divides n evenly.
      If (and only if) n > 1 is prime, k = 1 and (thus) k - 1 = 0.
{     While the top of the first stack is non-zero:
  {}    Pop it.
}     This pops n if n is prime, n and k - 1 if n is composite.
(
  []    Yield the height h of the stack. h = 1 iff n is prime).
  {}    Pop 0.
)     Push h + 0 = h.
Dennis
la source
2
Vous n'avez pas besoin de faire apparaître le dernier 0 sur la pile, car la vérité 1 sur le dessus suffit; vous pouvez enregistrer deux octets de cette manière en supprimant le dernier {}.
Steven H.
1
Hm, je suis déchiré. D'un côté, la question dit que la sortie devrait consister uniquement en une valeur de vérité ou de fausseté et 1 0est constituée de deux valeurs. D'un autre côté, nous accepterions les tableaux tant que la langue les considère comme des vérités ou des faussetés et que plusieurs éléments de la pile sont ce qui se rapproche le plus de Brain-Flak. Cela vaut peut-être la peine de prendre ceci pour méta.
Dennis
J'ai vérifié auprès du créateur de Brain-Flak que 1 0c'est la vérité. chat.stackexchange.com/transcript/message/32746241#32746241
Steven H.
3
Méta discussion pertinente: La vérité dans Brain-Flak et les langages similaires basés sur des piles
Dennis
17

R, 37 29 octets

n=scan();cat(sum(!n%%1:n)==2)

Utilise la division d'essai. scan()lit un entier de STDIN et cat()écrit dans STDOUT.

Nous générons un vecteur de longueur nconstitué des entiers 1 à nmodulo n. Nous testons si chacun est égal à 0 en inversant ( !), qui renvoie une valeur logique vraie lorsque le nombre est égal à 0 et fausse lorsqu'elle est supérieure à 0. La somme d'un vecteur logique correspond au nombre d'éléments réels. Nous nous attendons à ce que les seuls modules non nuls étant 1 et n, on s'attend donc à une somme de 2.

Sauvegardé 8 octets grâce à flodel!

Alex A.
la source
Avec f=function(x)sum(!x%%1:x)==2vous pouvez le faire en 28 octets.
Mutador
2
@ AndréMuta Pour ce défi, toutes les soumissions doivent être des programmes complets plutôt que de simples fonctions. Merci pour la suggestion cependant.
Alex A.
17

TI-BASIC, 12 octets

2=sum(not(fPart(Ans/randIntNoRep(1,Ans

Assez simple. randIntNoRep(donne une permutation aléatoire de tous les entiers de 1 à Ans.

Cela plie un peu les règles; parce que les listes dans TI-BASIC sont limitées à 999 éléments que j'ai interprétés

supposons que l'entrée puisse être stockée dans votre type de données

Cela signifie que tous les types de données peuvent être supposés prendre en charge l’entrée. OP est d'accord avec cette interprétation.

Une solution de 17 octets qui fonctionne jusqu’à 10 ^ 12 environ:

2=Σ(not(fPart(Ans/A)),A,1,Ans
lirtosiast
la source
@toothbrush TI-BASIC est un langage à jetons . Ainsi, chaque jeton correspond à un octet, à l'exception de randIntNoRep(deux.
lirtosiast
+1 Ah, je n'ai jamais vu TL-BASIC auparavant. Merci de me le faire savoir
Brosse à dents le
1
Bien que ce soit un peu injuste, n'est-ce pas ...? Je devrais écrire une langue de golf ne nécessitant que 1 à 4 octets (l'ID de la question), puis les paramètres. Il choisira la première réponse dans une langue qu'il comprend, l'exécutera (en passant tous les paramètres) et renverra le résultat ... Je me demande si cela enfreint les règles? :-)
Brosse à dents le
@toothbrush Dans la défense de TI-BASIC: pour l'interprète, ce n'est pas plus injuste que Pyth et les commandes à un caractère de CJam, et TI-BASIC est plus lisible.
lirtosiast
1
Vrai. Je n'aime pas ce genre de langage, car les solutions dans presque toutes les autres langues sont plus longues ... même si j'ai récemment battu CJam avec VB6 ! : -]
Brosse à dents le
15

PARI / GP, 21 octets

print(isprime(input))

Fonctionne pour des entrées ridiculement grandes, parce que ce genre de choses est fait pour PARI / GP.

Lynn
la source
6
isprimefait une preuve de primalité APR-CL, donc ralentit un peu car les entrées deviennent très grandes. ispseudoprime(input)effectue un test principal probable AES BPSW, qui sera beaucoup plus rapide pour plus de 100 chiffres. Toujours pas de contre-exemples connus après 35 ans. La version 2.1 et les versions antérieures de Pari, antérieures à 2002, utilisent une méthode différente qui peut facilement donner de faux résultats, mais personne ne devrait l’utiliser.
DanaJ
15

TI-BASIC, 24 octets

Notez que les programmes TI-Basic utilisent un système de jetons. Par conséquent, le comptage des caractères ne renvoie pas la valeur en octets réelle du programme.

Réponse positive de Thomas Kwa , elle est supérieure.

:Prompt N
:2
:While N≠1 and fPart(N/Ans
:Ans+1
:End
:N=Ans

Échantillon:

N=?1009
                         1
N=?17
                         1
N=?1008
                         0
N=?16
                         0

Maintenant, retourne 0s'il n'y a pas de prime, ou 1s'il l'est.

Zenohm
la source
3
La racine carrée n'est-elle pas simplement une optimisation dont vous n'avez pas réellement besoin pour que le programme soit correct?
Martin Ender
Pourquoi auriez-vous besoin de diviser par deux?
Geobits
J'aime toujours les réponses TI-BASIC.
Grant Miller
15

Stack Cats , 62 + 4 = 66 octets

*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]

Doit être exécuté avec les -lnindicateurs de ligne de commande (donc +4 octets). Impressions0 pour les nombres composés et 1pour les nombres premiers.

Essayez-le en ligne!

Je pense que c'est le premier programme non-trivial de Stack Cats.

Explication

Une rapide introduction à Stack Cats:

  • Stack Cats fonctionne sur une bande infinie de piles, avec une tête de bande pointant vers une pile en cours. Chaque pile est initialement remplie d'une quantité infinie de zéros. Je vais généralement ignorer ces zéros dans mon libellé. Par conséquent, lorsque je dis "le bas de la pile", je veux dire la valeur la plus basse non nulle et si je dis "la pile est vide", je veux dire qu'il n'y a que des zéros.
  • Avant que le programme ne commence, a -1est placé sur la pile initiale, puis toute l'entrée est poussée dessus. Dans ce cas, en raison de l' -nindicateur, l'entrée est lue sous forme d'entier décimal.
  • À la fin du programme, la pile actuelle est utilisée pour la sortie. S'il y a un -1en bas, il sera ignoré. De nouveau, en raison de l' -nindicateur, les valeurs de la pile sont simplement imprimées sous forme d'entiers décimaux séparés par des sauts de ligne.
  • Stack Cats est un langage de programme réversible: chaque morceau de code peut être annulé (sans que Stack Cats conserve la trace d’un historique explicite). Plus spécifiquement, pour inverser un morceau de code, il vous suffit de le refléter, par exemple, <<(\-_)devient (_-/)>>. Cet objectif de conception impose des restrictions assez sévères sur les types d'opérateurs et de constructions de flux de contrôle existant dans le langage, ainsi que sur les types de fonctions que vous pouvez calculer sur l'état de la mémoire globale.

  • Pour couronner le tout, chaque programme Stack Cats doit être symétrique. Vous remarquerez peut-être que ce n'est pas le cas pour le code source ci-dessus. C’est à cela que sert le -ldrapeau: il reflète implicitement le code à gauche, en utilisant le premier caractère du centre. Le programme actuel est donc le suivant:

    [<(*>=*(:)*[(>*{[[>[:<[>>_(_-<<(-!>)>(>-)):]<^:>!->}<*)*[^:<)*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]

Programmer efficacement avec l'ensemble du code est hautement non trivial et peu intuitif et n'a pas encore vraiment compris comment un humain peut le faire. Nous avons forcé ce programme pour des tâches plus simples, mais nous n'aurions pas pu nous en approcher à la main. Heureusement, nous avons trouvé un modèle de base qui vous permet d’ignorer la moitié du programme. Bien que cela soit certainement sous-optimal, c'est actuellement le seul moyen connu de programmer efficacement dans Stack Cats.

Donc, dans cette réponse, le modèle de ce motif est le suivant (la façon dont il est exécuté varie):

[<(...)*(...)>]

Lorsque le programme démarre, la bande de pile ressemble à ceci (pour une entrée 4, par exemple):

     4    
... -1 ...
     0
     ^

Le [déplace le haut de la pile vers la gauche (et la tête de la bande le long) - nous appelons cela "pousser". Et les <mouvements de la tête de la bande seule. Donc, après les deux premières commandes, nous avons cette situation:

...   4 -1 ...
    0 0  0
    ^

Maintenant, (...)c’est une boucle qui peut être utilisée assez facilement comme condition: la boucle n’est entrée et laissée que lorsque le sommet de la pile actuelle est positif. Depuis, il est actuellement nul, nous sautons toute la première moitié du programme. Maintenant, la commande centrale est *. C’est simplement XOR 1, c’est-à-dire qu’elle bascule le bit le moins significatif du haut de la pile et, dans ce cas, transforme le 0en 1:

... 1 4 -1 ...
    0 0  0
    ^

Maintenant, nous rencontrons l'image miroir du (...). Cette fois , le sommet de la pile est positive et nous faire entrer dans le code. Avant de regarder ce qui se passe entre les parenthèses, laissez-moi vous expliquer comment nous allons terminer à la fin: nous voulons nous assurer que, à la fin de ce bloc, nous avons à nouveau la tête de la bande sur une valeur positive boucle se termine après une seule itération et est simplement utilisée comme condition linéaire), que la pile à droite contient la sortie et que la pile à droite de celle-ci contient un -1. Si c'est le cas, nous quittons la boucle, passons >à la valeur de sortie et la ]plaçons sur la -1pile afin d'obtenir une pile vierge pour la sortie.

C'est ça. Maintenant, entre parenthèses, nous pouvons faire ce que nous voulons pour vérifier la primalité tant que nous nous assurons que nous organisons les choses comme décrit dans le paragraphe précédent à la fin (ce qui peut facilement être fait en poussant et en déplaçant la tête de la bande). J'ai d'abord essayé de résoudre le problème avec le théorème de Wilson, mais j'ai finalement dépassé les 100 octets, car le calcul factoriel au carré est en fait assez coûteux dans Stack Cats (du moins, je n'ai pas trouvé le moindre moyen). J'ai donc choisi la division d'essai et cela s'est avéré beaucoup plus simple. Regardons le premier bit linéaire:

>:^]

Vous avez déjà vu deux de ces commandes. En outre, :échange les deux valeurs supérieures de la pile actuelle et ^XOR la ​​deuxième valeur en valeur supérieure. Cela crée :^un modèle courant pour dupliquer une valeur sur une pile vide (nous tirons un zéro au-dessus de la valeur puis transformons le zéro en valeur 0 XOR x = x). Ainsi, après cela, notre bande ressemble à ceci:

         4    
... 1 4 -1 ...
    0 0  0
         ^

L'algorithme de division d'essai que j'ai implémenté ne fonctionne pas en entrée 1, nous devrions donc ignorer le code dans ce cas. Nous pouvons facilement mapper 1vers 0et tout le reste avec des valeurs positives *, alors voici comment nous procédons:

*(*...)

C’est-à-dire que nous nous tournons 1vers 0, sautons une grande partie du code si nous obtenons effectivement 0, mais à l’intérieur, nous annulons immédiatement le code *afin que nous puissions récupérer notre valeur d’entrée. Nous devons simplement nous assurer à nouveau que nous aboutissons à une valeur positive à la fin des parenthèses afin qu'elles ne commencent pas en boucle. À l'intérieur du conditionnel, nous déplaçons une pile à droite avec le >, puis nous démarrons la boucle de division de test principale:

{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}

Les accolades (par opposition aux parenthèses) définissent un type de boucle différent: il s'agit d'une boucle do-while, ce qui signifie qu'elle s'exécute toujours pour au moins une itération. L'autre différence est la condition de fin: lors de l'entrée dans la boucle, Stack Cat se souvient de la valeur maximale de la pile actuelle ( 0dans notre cas). La boucle sera ensuite exécutée jusqu'à ce que cette même valeur soit revue à la fin d'une itération. C'est pratique pour nous: à chaque itération, nous calculons simplement le reste du prochain diviseur potentiel et le déplaçons sur cette pile sur laquelle nous démarrons la boucle. Lorsque nous trouvons un diviseur, le reste l'est 0et la boucle s'arrête. Nous allons essayer les diviseurs à partir de n-1, puis les décrémenter 1. Cela signifie a) nous savons que cela se terminera lorsque nous atteindrons1 plus tard et b) nous pouvons ensuite déterminer si le nombre est premier ou non en inspectant le dernier diviseur que nous avons essayé (si c’est1, c’est un excellent, sinon ce n’est pas le cas).

Allons-y. Il y a une courte section linéaire au début:

<-!<:^>[:

Vous savez ce que la plupart de ces choses font maintenant. Les nouvelles commandes sont -et !. Stack Cats n'a pas d'opérateur d'incrémentation ou de décrémentation. Cependant, il a -(négation, c'est-à-dire multiplier par -1) et !(PAS au niveau du bit, c'est-à-dire multiplier par -1et décrémenter). Ceux-ci peuvent être combinés en incrément !-, ou décrément -!. Donc, nous décrémentons la copie de ndessus -1, puis faisons une autre copie de nla pile à gauche, puis récupérons le nouveau diviseur d’essai et le plaçons en dessous n. Donc, à la première itération, nous obtenons ceci:

      4       
      3       
... 1 4 -1 ...
    0 0  0
      ^

Lors des itérations suivantes, la 3volonté sera remplacée par le prochain diviseur de test, etc. (alors que les deux copies de nseront toujours la même valeur à ce stade).

((-<)<(<!-)>>-_)

C'est le calcul modulo. Puisque les boucles se terminent sur des valeurs positives, l’idée est de commencer -net d’y ajouter de manière répétée le diviseur d’essai djusqu’à obtenir une valeur positive. Une fois que nous faisons, nous soustrayons le résultat de det cela nous donne le reste. Le problème ici est que nous ne pouvons pas simplement placer un -nsommet de la pile et lancer une boucle qui ajoute d: si le haut de la pile est négatif, la boucle ne sera pas entrée. Telles sont les limites d'un langage de programmation réversible.

Donc, pour contourner ce problème, nous commençons par nen haut de la pile, mais nous le nions seulement à la première itération. Encore une fois, cela semble plus simple que cela s'avère être ...

(-<)

Lorsque le sommet de la pile est positif (c'est-à-dire uniquement à la première itération), nous le nions avec -. Cependant, nous ne pouvons pas le faire (-)parce que nous ne serions pas quittions la boucle jusqu'à ce que -a été appliquée deux fois. Donc, nous déplaçons une cellule avec <parce que nous savons qu’il ya une valeur positive (la 1). Ok, alors maintenant nous avons nié de manière fiable nla première itération. Mais nous avons un nouveau problème: la tête de la bande est maintenant dans une position différente lors de la première itération. Nous devons consolider cela avant de continuer. La prochaine <déplace la tête de la bande à gauche. La situation à la première itération:

        -4       
         3       
...   1  4 -1 ...
    0 0  0  0
    ^

Et à la deuxième itération (rappelez-vous que nous avons ajouté dune fois -nmaintenant):

      -1       
       3       
... 1  4 -1 ...
    0  0  0
    ^

Le conditionnel suivant fusionne à nouveau ces chemins:

(<!-)

Lors de la première itération, la tête de la bande pointe à zéro et est donc entièrement ignorée. Lors de nouvelles itérations, la tête de la bande pointe sur une unité, nous l'exécutons donc, nous nous déplaçons à gauche et incrémentons la cellule à cet endroit. Comme nous savons que la cellule commence à zéro, elle sera désormais toujours positive pour pouvoir quitter la boucle. Cela garantit que nous finissons toujours par deux piles à gauche de la pile principale et que nous pouvons maintenant revenir en arrière >>. Ensuite, à la fin de la boucle modulo, nous le faisons -_. Tu sais déjà -. _est de soustraction ce qui ^est de XOR: si le haut de la pile est aet la valeur est au- dessous bil remplace aavec b-a. Depuis que nous avons tout d'abord nié a, -_remplace apar dans notre total cumulé.b+a , ajoutant ainsid

Une fois la boucle terminée (nous avons atteint une valeur positive), la bande ressemble à ceci:

        2       
        3       
... 1 1 4 -1 ...
    0 0 0  0
        ^

La valeur la plus à gauche peut être n'importe quel nombre positif. En fait, c'est le nombre d'itérations moins un. Il y a un autre bit linéaire court maintenant:

_<<]>:]<]]

Comme je l'ai dit plus tôt, nous devons soustraire le résultat dpour obtenir le reste réel ( 3-2 = 1 = 4 % 3), nous le faisons donc _une fois de plus. Ensuite, nous devons nettoyer la pile que nous avons incrémentée à gauche: lorsque nous essayons le prochain diviseur, il doit être à nouveau égal à zéro pour que la première itération fonctionne. Nous nous déplaçons donc là-bas et plaçons cette valeur positive sur l'autre pile d'assistance <<], puis revenons sur notre pile opérationnelle avec une autre >. Nous nous arrêtons davec :et le repoussons sur -1avec ]puis nous plaçons le reste sur notre pile conditionnelle avec <]]. C’est la fin de la boucle de division d’essai: elle se poursuit jusqu’à ce que nous obtenions un reste nul, auquel cas la pile à gauche contientnLe plus grand diviseur (autre que n).

Une fois la boucle terminée, il nous reste juste *<avant de rejoindre à nouveau les chemins avec l’entrée 1. Il *transforme simplement le zéro en un 1, ce dont nous avons besoin dans un instant, puis nous passons au diviseur avec <(pour que nous soyons sur la même pile que pour l’entrée 1).

À ce stade, il est utile de comparer trois types d’entrées différents. Premièrement, le cas spécial n = 1où nous n’avons rien fait de ce genre de division:

         0    
... 1 1 -1 ...
    0 0  0
         ^

Ensuite, notre exemple précédent n = 4, un nombre composé:

    2           
    1    2 1    
... 1 4 -1 1 ...
    0 0  0 0
         ^

Et enfin, n = 3un nombre premier:

    3           
    1    1 1    
... 1 3 -1 1 ...
    0 0  0 0
         ^

Donc, pour les nombres premiers, nous avons un 1sur cette pile, et pour les nombres composés, nous avons un 0nombre positif ou supérieur à 2. Nous transformons cette situation en 0ou 1nous avons besoin avec le code final suivant:

]*(:)*=<*

]pousse simplement cette valeur vers la droite. Ensuite , *est utilisé pour simplifier la situation conditionnelle fortement: en activant le moins important, nous nous tournons 1(premier) en 0, 0(composite) dans la valeur positive 1, et toutes les autres valeurs positives restent toujours positives. Il ne reste plus qu’à faire la distinction entre 0positif et positif. C'est là que nous en utilisons un autre (:). Si le haut de la pile est 0(et que l'entrée était un nombre premier), ceci est simplement ignoré. Mais si le sommet de la pile est positif (et l’entrée était un nombre composite), elle est échangée avec le 1, de sorte que nous avons maintenant 0pour composite et1pour les nombres premiers - seulement deux valeurs distinctes. Bien sûr, ils sont le contraire de ce que nous voulons produire, mais cela se corrige facilement avec un autre *.

Maintenant , tout ce qui reste est de restaurer le modèle des piles attendues par notre cadre environnant: la tête de bande sur une valeur positive, résultat au - dessus de la pile à droite, et un seul -1sur la droite de la pile de ce . C'est à quoi ça =<*sert. =permute les sommets des deux piles adjacentes, ce qui déplace le -1vers la droite du résultat, par exemple, pour une 4nouvelle saisie :

    2     0       
    1     3       
... 1 4   1 -1 ...
    0 0 0 0  0
          ^

Ensuite, nous passons à gauche avec <et transformons ce zéro en un avec *. Et c'est ça.

Si vous souhaitez approfondir le fonctionnement du programme, vous pouvez utiliser les options de débogage. Ajoutez l’ -dindicateur et insérez-le "où vous voulez voir l’état actuel de la mémoire, par exemple , ou utilisez l’ -Dindicateur pour obtenir une trace complète du programme entier . Sinon, vous pouvez utiliser EsotericIDE de Timwi, qui inclut un interpréteur Stack Cats avec un débogueur pas à pas.

Martin Ender
la source
3
>:^]devrait être le logo officiel de Stack Cats
Alex A.
14

Haskell, 54 octets

import Data.Numbers.Primes
main=readLn>>=print.isPrime

Rien à expliquer.

nimi
la source
1
Le même score peut être atteint (bien que très inefficacement) sans bibliothèques externes, en utilisant le théorème de Wilson:main=do n<-readLn;print$n>1&&mod(product[1..n-1]+1)n<1
Lynn
9
On peut même faire plus court: main=do n<-readLn;print$mod(product[1..n-1]^2)n>0soit 49 octets.
Lynn
4
@Mauris: Nice. S'il vous plaît poster comme une réponse séparée.
Nimi
14

Ruby, 15 + 8 = 23 octets

p$_.to_i.prime?

Échantillon échantillon:

bash-4.3$ ruby -rprime -ne 'p$_.to_i.prime?' <<< 2015
false
homme au travail
la source
Heheh, je savais qu'il y aurait un Rubin intégré quelque part, mais je ne pouvais pas être dérangé de le chercher, alors j'ai répondu en C. +1.
Level River St
@steveverrill, je le savais car c'était une aide précieuse pour Project Euler.
manatwork
14

JavaScript, 39 36 octets

3 octets sauvés grâce à ETHproductions:

for(i=n=prompt();n%--i;);alert(1==i)

Affiche true pour un nombre premier, false sinon.

La boucle for teste chaque nombre i de n-1 jusqu'à ce que i soit un diviseur. Si le premier diviseur trouvé est 1, il s'agit d'un nombre premier.

Solution précédente (39 octets):

for(i=n=prompt();n%--i&&i;);alert(1==i)

Comment a été laissé un test inutile:

for(i=2,n=prompt();n%i>0&&i*i<n;i++);alert(n%i>0) //49: Simple implementation: loop from 2 to sqrt(n) to test the modulo.
for(i=2,n=prompt();n%i>0&&i<n;i++);alert(n==i)    //46: Replace i*i<n by i<n (loop from 2 to n) and replace n%i>0 by n==i
for(i=2,n=prompt();n%i&&i<n;i++);alert(n==i)      //44: Replace n%i>0 by n%i
for(i=2,n=prompt();n%i&&i++<n;);alert(n==i)       //43: Shorten loop increment
for(i=n=prompt();n%--i&&i>0;);alert(1==i)         //41: Loop from n to 1. Better variable initialization.
for(i=n=prompt();n%--i&&i;);alert(1==i)           //39: \o/ Replace i>0 by i

Je n'ai posté que la solution de 39 octets car la meilleure réponse JavaScript était déjà de 40 octets.

Hedi
la source
2
Bienvenue dans Programming Puzzles & Code Golf!
Dennis
2
Très bonne réponse! Le &&ine fait réellement rien dans ce programme, vous pouvez donc le supprimer.
ETHproductions
devrait ajouter n>1à la condition finale cependant, si vous ne voulez 1pas être premier.
Titus
1
@Titus Si l'entrée est 1la boucle for, elle le fera n%--iune fois: 1%0retourne NaNet arrête la boucle. Quand alertest appelé iest déjà égal à 0si 1==irenvoie false.
Hedi
2
i <2 (et du texte)
Scheintod
13

Escargots, 122

Les entrées doivent être données à l'unaire. Les chiffres peuvent être n’importe quel mélange de caractères, sauf les nouvelles lignes.

^
..~|!(.2+~).!~!{{t.l=.r=.}+!{t.!.!~!{{r!~u~`+(d!~!.r~)+d~,.r.=.(l!~u~)+(d!~l~)+d~,.l.},l=(.!.)(r!~u~)+(d!~!.r~)+d~,.r.!.

Dans cette langue de correspondance de modèle 2D, l'état du programme se compose uniquement de l'emplacement actuel de la grille, de l'ensemble de cellules qui ont été appariées et de la position dans le code de modèle. Il est également illégal de se rendre sur une place assortie. C'est délicat, mais il est possible de stocker et de récupérer des informations. La restriction empêchant de voyager sur une cellule appariée peut être surmontée en faisant un retour en arrière, en se téléportant (t ) et en des assertions ( =, !) qui laissent la grille inchangée une fois terminée.

Factorisation de 25

La factorisation pour un nombre composé impair commence par délimiter un ensemble de cellules non adjacentes (bleu dans le diagramme). Ensuite, à partir de chaque cellule jaune, le programme vérifie qu’il existe un nombre égal de cellules non bleues de chaque côté de la cellule bleue adjacente en effectuant des va-et-vient entre les deux côtés. Le diagramme montre ce motif pour l’une des quatre cellules jaunes à vérifier.

Code annoté:

^                         Match only at the first character
..~ |                     Special case to return true for n=2
!(.2 + ~)                 Fail for even numbers
. !~                      Match 1st character and fail for n=1
!{                        If the bracketed pattern matches, it's composite.
  (t. l=. r=. =(.,~) )+   Teleport to 1 or more chars and match them (blue in graphic)
                          Only teleport to ones that have an unmatched char on each side.
                          The =(.,~) is removed in the golfed code. It forces the
                          teleports to proceed from left to right, reducing the
                          time from factorial to exponential.
  !{                      If bracketed pattern matches, factorization has failed.
    t . !. !~             Teleport to a square to the left of a blue square (yellow in diagram)
    !{                    Bracketed pattern verifies equal number of spaces to
                          the left or right of a blue square.
      {              
        (r!~ u~)+         Up...
        (d!~!. r~)+       Right...
        d~,               Down...
        . r . =.          Move 1 to the right, and check that we are not on the edge;
                          otherwise d~, can fall off next iteration and create and infinite loop
        (l!~ u~)+         Up...
        (d!~ l~)+         Left...
        d ~,              Down...
        . l .             Left 1
      } ,                 Repeat 0 or more times
      l  =(. !.)          Check for exactly 1 unused char to the left
      (r!~ u~)+           Up...
      (d!~!. r~)+         Right...
      d ~,                Down...
      . r . !.
    }
  }
}
feersum
la source
13

C, 67 octets

i,n;main(p){for(scanf("%d",&i),n=i;--i;p=p*i*i%n);putchar(48+p%n);}

Prints !1(une valeur falsey, selon la définition de Peter Taylor ) 0 si (n-1)!^2 == 0 (mod n)et 1autrement.

EDIT : Après quelques discussions sur le chat, puts("!1"+p%n)semble être considéré comme un peu triché, donc je l'ai remplacé. Le résultat est un octet plus long.

EDIT : Fixe pour les grandes entrées.

Des solutions plus courtes

56 octets : comme recommandé dans les commentaires de pawel.boczarski, je pouvais prendre des entrées unaires en lisant le nombre d'arguments de la ligne de commande:

p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);putchar(48+p%n);}

invoquer le programme comme

$ ./a.out 1 1 1 1 1
1                        <-- as 5 is prime

51 octets : Si vous autorisez la "sortie" au moyen de codes de retour:

p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);return p%n;}
Lynn
la source
Votre solution pourrait être raccourcie à l'aide d'une représentation unaire (nombre d'arguments en ligne de commande), comme dans ma solution publiée. Vous pouvez supprimer quelques octets lors d'un appel à scanf.
pawel.boczarski
puts("!1"+p%n)Comment pourriez-vous faire a+bpour les char*valeurs?
Erik the Outgolfer
Si la chaîne "!1"commence à l'adresse a, alors a+1vous la trouverez "1".
Lynn
@ Lynn Oh, je pensais que c'était pour la concaténation (ouais, mieux vaut laisser cela à strcat(const char*,const char*).)
Erik the Outgolfer
Pourriez-vous changer p=p*i*i%npourp*=i*i%n
Albert Renshaw le
12

Python 3, 59 octets

Utilise maintenant les input()arguments de la ligne de commande. Merci à @Beta Decay

n=int(input())
print([i for i in range(1,n)if n%i==0]==[1])
uno20001
la source
L'utilisation des entrées input()serait beaucoup plus courte
Beta Decay
Merci, j'ai déjà écrit avec using of input (), mais j'ai oublié d'actualiser ma réponse. Merci encore!
uno20001
4
52 octets: n=m=int(input()),print(all(n%m for m in range(2,n)))
John Lyon
1
Es-tu sérieux. Passez 25 caractères supplémentaires pour une accélération boiteuse du second degré? Ici, nous détestons les octets . Nous passons chaque heure, minute et seconde de notre vie à nous débarrasser du dix-neuvième octet. (Je plaisante. Mais nous ne faisons pas d'optimisations de temps qui augmentent la durée du programme.)
CalculatorFeline
2
Utilisez à la n%i<1place.
Erik the Outgolfer
12

APL, 40 à 13 octets

2=+/0=x|⍨⍳x←⎕

Section de première instance avec le même algorithme que ma réponse R . Nous xaffectons l'entrée de STDIN ( ⎕) et obtenons le reste xdivisé par chaque entier compris entre 1 et x. Chaque reste est comparé à 0, ce qui nous donne un vecteur de uns et de zéros indiquant quels nombres entiers se divisent x. Ceci est résumé en utilisant +/pour obtenir le nombre de diviseurs. Si ce nombre est exactement 2, cela signifie que les seuls diviseurs sont 1 et x, et xest donc premier.

Alex A.
la source
12

Python 2, 44

P=n=1
exec"P*=n*n;n+=1;"*~-input()
print P%n

Comme la réponse Python de Sp3000 , mais évite de stocker l'entrée en comptant la variable njusqu'à 1la valeur d'entrée.

Xnor
la source
12

Métaprogrammation de modèles C ++. 166 131 119 octets.

Le code est compilé si la constante est un nombre premier et non pas si composite ou 1.

template<int a,int b=a>struct t{enum{x=t<a,~-b>::x+!(a%b)};};
template<int b>struct t<b,0>{enum{x};};
int _[t<1>::x==2];

(Toutes les nouvelles lignes, sauf la dernière, sont éliminées dans la version "réelle").

Je pense que "l'échec de la compilation" est une valeur de retour de Falsey pour un langage de métaprogrammation. Notez que cela ne lie pas (donc si vous le nourrissez bien, vous obtiendrez des erreurs de liaison) en tant que programme C ++ complet.

La valeur à tester est l'entier de la dernière "ligne".

exemple en direct .

Yakk
la source