¿Es este número un primo?

195

Lo creas o no, todavía no tenemos un desafío de código de golf para una simple prueba de primalidad . Si bien puede que no sea el desafío más interesante, particularmente para los idiomas "usuales", puede no ser trivial en muchos idiomas.

El código de Rosetta presenta listas por idioma de enfoques idiomáticos para las pruebas de primalidad, una que usa la prueba de Miller-Rabin específicamente y otra que usa la división de prueba . Sin embargo, "más idiomático" a menudo no coincide con "más corto". En un esfuerzo por hacer de Programming Puzzles y Code Golf el sitio de referencia para el golf de código, este desafío busca compilar un catálogo del enfoque más corto en todos los idiomas, similar a "¡Hola, Mundo!" y Golf un quine por gran bien! .

Además, la capacidad de implementar una prueba de primalidad es parte de nuestra definición de lenguaje de programación , por lo que este desafío también servirá como un directorio de lenguajes de programación probados.

Tarea

Escriba un programa completo que, dado un entero estrictamente positivo n como entrada, determine si n es primo e imprima un valor verdadero o falso en consecuencia.

Para el propósito de este desafío, un número entero es primo si tiene exactamente dos divisores estrictamente positivos. Tenga en cuenta que esto excluye a 1 , que es su único divisor estrictamente positivo.

Su algoritmo debe ser determinista (es decir, producir la salida correcta con probabilidad 1) y, en teoría, debería funcionar para enteros arbitrariamente grandes. En la práctica, puede suponer que la entrada se puede almacenar en su tipo de datos, siempre que el programa funcione para enteros del 1 al 255.

Entrada

  • Si su idioma puede leer desde STDIN, aceptar argumentos de la línea de comandos o cualquier otra forma alternativa de entrada del usuario, puede leer el entero como su representación decimal, representación unaria (usando un carácter de su elección), matriz de bytes (grande o little endian) o un solo byte (si este es el tipo de datos más grande de su idioma).

  • Si (y solo si) su idioma no puede aceptar ningún tipo de entrada del usuario, puede codificar la entrada en su programa.

    En este caso, el número entero codificado debe ser fácilmente intercambiable. En particular, puede aparecer solo en un solo lugar en todo el programa.

    Para fines de puntuación, envíe el programa que corresponde a la entrada 1 .

Salida

La salida debe escribirse en STDOUT o en la alternativa más cercana.

Si es posible, la salida debe consistir únicamente en un valor verdadero o falso (o una representación de cadena del mismo), opcionalmente seguido de una nueva línea nueva.

La única excepción a esta regla es la salida constante del intérprete de su idioma que no se puede suprimir, como un saludo, códigos de color ANSI o sangría.

Reglas adicionales

  • No se trata de encontrar el idioma con el enfoque más corto para las pruebas principales, se trata de encontrar el enfoque más corto en cada idioma. Por lo tanto, ninguna respuesta se marcará como aceptada.

  • Las presentaciones en la mayoría de los idiomas se puntuarán en bytes en una codificación preexistente apropiada, generalmente (pero no necesariamente) UTF-8.

    El idioma Piet , por ejemplo, se puntuará en codeles, que es la elección natural para este idioma.

    Algunos idiomas, como las carpetas , son un poco difíciles de puntuar. En caso de duda, por favor pregunte en el Meta .

  • A diferencia de nuestras reglas habituales, siéntase libre de usar un idioma (o versión de idioma) incluso si es más nuevo que este desafío. Si alguien quiere abusar de esto creando un lenguaje donde el programa vacío realiza una prueba de primalidad, felicidades por allanar el camino para una respuesta muy aburrida.

    Tenga en cuenta que debe haber un intérprete para que se pueda probar el envío. Se permite (e incluso se recomienda) escribir este intérprete usted mismo para un idioma previamente no implementado.

  • Si su idioma de elección es una variante trivial de otro lenguaje (potencialmente más popular) que ya tiene una respuesta (piense en dialectos BASIC o SQL, shells Unix o derivados triviales de Brainfuck como Headsecks o Unary), considere agregar una nota a la respuesta existente que la misma solución o una muy similar también es la más corta en el otro idioma.

  • Se permiten funciones integradas para probar la originalidad . Este desafío tiene la intención de catalogar la solución más corta posible en cada idioma, por lo que si es más corto usar un incorporado en su idioma, hágalo.

  • A menos que se hayan anulado anteriormente, se aplican todas las reglas estándar de código de golf , incluido http://meta.codegolf.stackexchange.com/q/1061 .

Como nota al margen, no desestime las respuestas aburridas (pero válidas) en idiomas donde no hay mucho para jugar golf; todavía son útiles para esta pregunta, ya que trata de compilar un catálogo lo más completo posible. Sin embargo, sobre todo vota las respuestas en idiomas en los que el autor realmente tuvo que esforzarse para jugar golf en el código.

Catalogar

El Fragmento de pila al final de esta publicación genera el catálogo a partir de las respuestas a) como una lista de la solución más corta por idioma yb) como una tabla de clasificación general.

Para asegurarse de que su respuesta se muestre, comience con un título, utilizando la siguiente plantilla de Markdown:

## Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

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

Si desea incluir varios números en su encabezado (por ejemplo, porque su puntaje es la suma de dos archivos o desea enumerar las penalizaciones de la bandera del intérprete por separado), asegúrese de que el puntaje real sea el último número en el encabezado:

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

También puede hacer que el nombre del idioma sea un enlace que luego aparecerá en el fragmento:

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

Mostrar fragmento de código

code-golf number number-theory primes decision-problem Dennis
fuente
¿Puedo tomar entradas como números negativos, donde abs (input) sería el número que estoy probando?
Stan Strum
No, la entrada es un entero estrictamente positivo.
Dennis
1
@LyndonWhite Esto pretendía ser un catálogo (como "¡Hola, Mundo!" ) De pruebas de primalidad, por lo que parecía preferible un formato de presentación unificado. Es una de las dos decisiones sobre este desafío que lamento, y la otra solo permite las pruebas de primitivismo deterministas.
Dennis
1
@Shaggy Parece una pregunta para meta.
Dennis
1
Sí, eso es lo que estaba pensando. Te dejaré hacer los honores, ya que es tu desafío.
Shaggy

Respuestas:

226

¡Hola Mundo! 13

hello, world!
histocrat
fuente
83
¿Usted, como, simplemente crear esta lengua, justo para esta presentación? ;)
ETHproductions
41
@ETHproductions Parece que la última confirmación fue hace 10 días.
Geobits
39
Esperaba tener el idioma en una forma ligeramente mejor antes de vincularlo a cualquier parte, pero este desafío fue publicado y no pude resistirme.
histocrat
31
Casi diría que colgar en una entrada de 1 es la funcionalidad correcta.
iamnotmaynard
22
La mejor parte de esto es que el programa no es solo incorporado, cada personaje juega su propio papel para obtener el resultado correcto.
ETHproductions
157

Hexagonía , 29 bytes.

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

La versión legible de este código es:

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

Explicación: Comprueba si hay un número de 2 a n-1 que divide n.

Inicializacion:

Escriba n en una celda de memoria y n-1 en otra:

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

Caso especial n = 1:

Imprime un 0 y termina

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

El lazo

Calcule n% a y disminuya a. Termine si a = 1 o n% a = 0.

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

Caso a = 1:

Aumente un 0 a un 1, imprímalo y finalice. (El puntero de instrucciones se ejecuta en dirección NE y recorre los bucles desde la esquina este hasta la esquina sudoeste. Y $ se asegura de que ignora el siguiente comando)

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

Caso a% n = 0:

Imprima el 0 y termine (el puntero de instrucciones está ejecutando SW y recorre en bucle a la parte superior a la @

   . . . .
  . . @ . .
 . . . . . >
. . . . . ! .
 . . . . . .
  . . . . .
   . . . .
Etoplay
fuente
61
Santa mierda, esa es una impresionante primera publicación. :) Ahora pondré la recompensa (la otorgaré en 7 días, para llamar más la atención sobre su respuesta). Bienvenido a PPCG!
Martin Ender
35
¡Gran respuesta! +1 para " La versión legible de este código es: <...> " :-)
hasta el
68

Hexagonía , 218 92 58 55 bytes

Aviso: Etoplay ha superado esta respuesta con una solución 4 de longitud lateral.

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

¡El primer programa de hexagonía no trivial (es decir, no lineal)! Se basa en el mismo enfoque factorial al cuadrado que la respuesta Laberinto de Sp3000 . Después de comenzar con un hexágono de la talla 10, me las arreglé para comprimirlo hasta un tamaño 5. Sin embargo, yo era capaz de volver a utilizar un código duplicado y todavía hay un buen montón de no-ops en el código, por lo que el tamaño 4 podría simplemente ser posible.

Explicación

Para darle sentido al código, primero tenemos que desplegarlo. Hexagony agrega cualquier código fuente al siguiente número hexagonal centrado con no-ops ( .), que es 61. Luego reorganiza el código en un hexágono regular del tamaño correspondiente:

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

Esto es bastante complejo con rutas de ejecución cruzadas y superpuestas y múltiples punteros de instrucción (IP). Para explicar cómo funciona, primero veamos una versión no protegida donde el flujo de control no pasa por los bordes, solo se usa una IP y las rutas de ejecución son lo más simples posible:

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

Nota al margen: el código anterior comienza con la ejecución de la primera línea, que está llena de no-ops. Luego, cuando la IP llega al borde noreste, se ajusta a la esquina más a la izquierda (el )), donde comienza el código real.

Antes de comenzar, una palabra sobre el diseño de memoria de Hexagony. Es un poco como la cinta de Brainfuck con esteroides. De hecho, no es una cinta, pero es una cuadrícula hexagonal en sí (una infinita), donde cada borde tiene un valor entero, que inicialmente es 0 (y a diferencia del Brainfuck estándar, los valores son enteros de precisión arbitraria con signo). Para este programa, usaremos cuatro aristas:

ingrese la descripción de la imagen aquí

Vamos a calcular el factorial en el borde Una , la cuenta atrás nuestra entrada en el borde C y almacenamos otra copia de la entrada (para el módulo) en el borde D . B se usa como un borde temporal para los cálculos.

El puntero de memoria (MP) comienza en el borde A y apunta hacia el norte (esto es importante para mover el MP). Ahora aquí está el primer bit del código:

)}?}=&{

)incrementos de borde A a 1como la base de la factorial. }hace que el MP gire a la derecha, es decir, se mueva hacia el borde C (apuntando hacia el noreste). Aquí leemos la entrada como un entero con ?. Luego tomamos otro giro a la derecha al borde D con }. =invierte el MP, de manera que señala en el vértice compartido con C . &copia el valor de C (la entrada) en D ; el valor se copia desde la izquierda porque el valor actual no es positivo (cero). Finalmente, hacemos que el MP gire a la izquierda de nuevo a C con {.

A continuación, <técnicamente es una rama, pero sabemos que el valor actual es positivo, por lo que la IP siempre girará a la derecha hacia >. Una rama golpeó por los actos secundarios como un espejo, de tal manera que la IP se mueve horizontalmente de nuevo, hacia el (, lo que disminuye el valor de C .

La siguiente rama, en realidad< es una rama ahora. Así es como nos desplazamos de abajo a abajo . Si bien el valor actual en C es positivo, la IP gira a la derecha (para ejecutar el bucle). Una vez que lleguemos a cero, en su lugar girará a la izquierda.n-11

Veamos el bucle "cuerpo". El |son espejos simples, el >y <también se utilizan como espejos de nuevo. Eso significa que el cuerpo del bucle real se reduce a

}=)&}=*}=

}mueve el MP al borde B , =invierte su dirección para enfrentar el vértice ABC . )incrementa el valor: esto solo es relevante para la primera iteración, donde el valor de B sigue siendo cero: queremos asegurarnos de que sea positivo, de modo que la siguiente instrucción &copie al vecino correcto , es decir , A , es decir, el valor actual del factorial cálculo, en B .

}luego mueve el MP a A , lo =invierte nuevamente para enfrentar el vértice común. *multiplica ambos vecinos, es decir, los bordes B y C y almacena el resultado en A . Finalmente, tenemos otro }=para volver a C , aún frente al vértice ABC .

Espero que puedan ver cómo esto calcula el factorial de n-1en una .

Así que ahora que lo hemos hecho, el contador de bucle en C es cero. Queremos cuadrar el factorial y luego tomar el módulo con la entrada. Eso es lo que hace este código:

&}=*{&'%!@

Desde C es cero, &copia el vecino de la izquierda, es decir, el factorial en A . }=*mueve a B y almacena el producto de las dos copias del factorial (es decir, el cuadrado) en B . {retrocede a C , pero no invierte el MP. Sabemos que el valor actual es ahora positiva, por lo que &de entrada copias de D a C . 'la MP hacia atrás a la derecha, es decir, en A . Recuerde, el cuadrado de la factorial está en B y la entrada está en C . Entonces %calcula (n-1)!^2 % n, exactamente lo que estamos buscando.!imprime el resultado como un entero (0 o 1) y @finaliza el programa.

De acuerdo, pero esa era la versión sin golf. ¿Qué pasa con la versión de golf? Necesita saber dos cosas más sobre Hexagony:

  1. Los bordes se envuelven. Si la IP golpea un borde del hexágono, salta al borde opuesto. Esto es ambiguo cuando la IP golpea una esquina en línea recta, por lo que golpear una esquina también actúa como una rama: si el valor actual es positivo, la IP salta al borde de la cuadrícula a su derecha, de lo contrario a la izquierda.
  2. En realidad hay 6 IPs. Cada uno de ellos comienza en una esquina diferente, moviéndose a lo largo del borde en el sentido de las agujas del reloj. Solo uno de ellos está activo a la vez, lo que significa que puede ignorar los otros 5 IP si no los quiere. Puede cambiar a la siguiente IP (en orden de las agujas del reloj) con ]y a la anterior con [. (También puede elegir uno específico con #, pero eso es para otro momento).

También hay algunos comandos nuevos en él: \y /son espejos |, y ~multiplica el valor actual por -1.

Entonces, ¿cómo se traduce la versión sin golf a la de golf? El código de configuración lineal )}?}=&{y la estructura básica del bucle se pueden encontrar aquí:

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

Ahora el cuerpo del bucle cruza los bordes varias veces, pero lo más importante, el cálculo real se transfiere a la IP anterior (que comienza en la esquina izquierda, moviéndose hacia el noreste):

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

Después de rebotar en la rama hacia el sureste, la IP se envuelve alrededor del borde hacia los dos =en la esquina superior izquierda (que, juntos, son un no-op), luego rebota en el /. El ~invierte el signo del valor de la corriente, que es importante para las iteraciones posteriores. La IP se envuelve alrededor del mismo borde nuevamente y finalmente golpea [donde el control se transfiere a la otra IP.

Este ahora ejecuta lo ~}=)&}=*}que deshace la negación y luego solo ejecuta el cuerpo del bucle sin golf (menos el =). Finalmente, toca ]qué control de manos vuelve a la IP original. (Tenga en cuenta que la próxima vez que ejecutemos esta IP, comenzará desde donde se quedó, por lo que primero llegará a la esquina. Necesitamos que el valor actual sea negativo para que la IP salte de nuevo al borde noroeste en lugar del sureste.)

Una vez que la IP original reanuda el control, rebota \, ejecuta el resto =y luego golpea >para alimentar la siguiente iteración del bucle.

Ahora la parte realmente loca: ¿qué sucede cuando termina el ciclo?

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

La IP se mueve hacia el noreste <y se envuelve hacia la diagonal noreste. Por lo tanto, termina en la misma ruta de ejecución que el cuerpo del bucle ( &}=*}]). Lo cual es realmente genial, porque ese es exactamente el código que queremos ejecutar en este punto, al menos si agregamos otro =}(porque }=}es equivalente a {). Pero, ¿cómo no vuelve a entrar en el ciclo anterior? Porque ]cambia a la siguiente IP, que ahora es la IP (hasta ahora no utilizada) que comienza en la esquina superior derecha, moviéndose hacia el sur oeste. A partir de ahí, la IP continúa a lo largo del borde, se ajusta a la esquina superior izquierda, se mueve hacia abajo en la diagonal, rebota |y termina @mientras ejecuta el bit final de código lineal:

=}&)('%!@

(El )(es un no-op, por supuesto, tuve que agregar el (porque )ya estaba allí).

Uf ... qué desastre ...

Martin Ender
fuente
¡Agradable! ¿Qué tan nuevo es esto? Además, es posible que desee crear una página de esolangs cada vez que obtenga una versión estable
mbomb007
18
@ mbomb007 Implementé el lenguaje hace dos días (y lo diseñé dos o tres días antes). Y sí, definitivamente agregaré una página de esolangs, pero creo que la especificación aún no es 100% estable (todavía hay 3 comandos no asignados, por ejemplo). Una vez que sienta que es más estable, lo agregaré tanto a esolangs como a nuestra meta publicación.
Martin Ender
Debajo del hex expandido se ajusta a la esquina más a la izquierda (la 1) . ¿De qué 1estás hablando allí?
mbomb007
@ mbomb007 arreglado. El )solía ser a 1.
Martin Ender
55
+1 solo por el nivel de detalle en tu explicación de cómo funciona. Si vinieran más idiomas con un ejemplo que detallara que más personas podrían usarlos: D
jdarling
66

Pyth, 4 bytes

}QPQ

Impresiones Trueo False.

orlp
fuente
12
Sé que esto es antiguo, pero ahora también puede hacerlo así: P_Q y guardar 1 byte.
drobilc
14
Ahora es posible conP_
Blue
3
@drobilc Puede cortar la Q, como un EOF cuando la función espera un argumento, utiliza la entrada
Stan Strum
55

Retina , 16 bytes

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

Pruébalo en línea!

Comencemos con un clásico: detectar primos con una expresión regular . La entrada debe darse en unario , utilizando cualquier carácter imprimible repetido. El conjunto de pruebas incluye una conversión de decimal a unario por conveniencia.

Un programa Retina que consiste en una sola línea trata esa línea como una expresión regular e imprime el número de coincidencias encontradas en la entrada, que será 0para números compuestos y números 1primos.

La búsqueda anticipada garantiza que la entrada no sea compuesta: el rastreo intentará cada subcadena posible (de al menos 2 caracteres) (..+), la búsqueda anticipada intentará coincidir con el resto de la entrada repitiendo lo que se capturó aquí. Si esto es posible, eso significa que la entrada tiene un divisor mayor que 1, pero que es menor que sí mismo. Si ese es el caso, la anticipación negativa hace que la coincidencia falle. Para los primos no existe tal posibilidad, y el partido continúa.

El único problema es que esta búsqueda anticipada también acepta 1, por lo que descartamos al unir al menos dos caracteres con ...

Martin Ender
fuente
Esa es en realidad una expresión irregular, ya que los números primos no forman un lenguaje regular.
PyRulez
@PyRulez La mayoría de los sabores de expresiones regulares del mundo real son mucho más poderosos que el concepto teórico de expresiones regulares. Aunque mejoré la redacción.
Martin Ender
1
Los motores "regex" más potentes a la vista en este momento tienen un poder de reconocimiento igual al de un autómata lineal. Regex de problema estándar, recursividad de patrones, lookhead ilimitado y lookback atrás ilimitado son todo lo que necesita para el análisis sensible al contexto (aunque las referencias inversas y tales generalmente ayudan a complicar el análisis eficiente), y algunos lo tienen todo. Ni siquiera me hagas comenzar con los motores que te permiten incrustar código en la expresión regular.
eaglgenes101
52

CJam, 4 bytes

qimp

CJam tiene un operador incorporado para pruebas de primalidad.

Peter Taylor
fuente
18
Alternativamente:limp
Sp3000
43
pimpmi cjam
flawr
12
pimpes objetivamente más proxeneta
MickLH
1
También puedes hacerlol~mp
vacas graznan el
12
@Cyoce, qlee una línea de entrada, la ianaliza como un número entero y mpestá integrada. CJam tiene dos grupos de dos personajes incorporados: los "extendidos" comienzan ey los "matemáticos" comienzanm
Peter Taylor
48

HTML + CSS, 254 + n máx. * 28 bytes

Podemos verificar la primalidad usando expresiones regulares. Mozilla tiene @document, que se define como:

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

Para filtrar elementos a través de CSS en función de la URL actual. Este es un solo pase, por lo que tenemos que hacer dos pasos:

  1. Obtenga aportes del usuario. Esta entrada debe reflejarse de alguna manera en la URL actual.
  2. Responda al usuario con el menor código posible.

1. Obteniendo entrada

La forma más corta que puedo imaginar para obtener información y transferirla a la URL es un GETformulario con casillas de verificación. Para la expresión regular, solo necesitamos una cadena única para contar las apariencias.

Entonces comenzamos con esto (61 bytes):

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

Tenemos dos <p>s únicos para indicar si el número ingresado es primo (1) o no (0). También definimos la forma y su acción.

Seguido de n max casillas de verificación con el mismo nombre (n max * 28 bytes):

<input type=checkbox name=i>

Seguido por el elemento de envío (34 bytes):

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

2. Mostrar respuesta

Necesitamos el CSS (159 bytes) para seleccionar la <p>visualización (1 o 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}}

»Pruébelo en codepen.io (solo firefox)

mınxomaτ
fuente
12
+1: Este es mi abuso favorito de HTML de todos los tiempos, y el tipo de cosas que me hacen amar el codegolf.
gato
Esto es ciertamente interesante, pero no estoy seguro si satisface las reglas de este desafío. En particular, no creo que cumpla con Su algoritmo [...] debería, en teoría, funcionar para enteros arbitrariamente grandes. ¿No podría usar también una expresión regular en el valor de un campo de entrada?
Dennis
@ Dennis Quizás. Probablemente incluso. Pero eso no resolvería el problema que mencionaste. Lo dejo aquí como una entrada no competitiva, porque este es el desafío más temático para eso.
mınxomaτ
Por qué no? Si tiene un número en unario en un campo de entrada, su código ya no dependerá del número máximo.
Dennis
55
Hm, pensé en esto un poco más, y realmente no hay diferencia entre tener solo x casillas de verificación y un intérprete que solo tiene números de y-bit. Haga caso omiso de mi comentario anterior.
Dennis
40

Hexagonía , 28 bytes.

Como Etoplay me derrotó absolutamente en esta pregunta , sentí que tenía que superar su otra respuesta .

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

Pruébalo en línea!

Utilizo el teorema de Wilson, como Martin hizo en su respuesta : dado n, produzco(n-1!)² mod n

Aquí se desarrolló el programa:

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

Y aquí está la versión legible :

Muy legible

Explicación:

El programa tiene tres pasos principales: inicialización , factorial y de salida .

El modelo de memoria de Hexagony es una cuadrícula hexagonal infinita. Estoy usando 5 ubicaciones de memoria, como se muestra en este diagrama:

Memoria

Me referiré a estas ubicaciones (y a los números enteros almacenados en ellas) por sus etiquetas en ese diagrama.

Inicialización

Inicialización

El puntero de instrucciones ( IP ) comienza en la esquina superior izquierda, hacia el este. El puntero de memoria ( MP ) comienza en IN .

Primero, ?lee el número de la entrada y lo almacena en IN . La IP permanece en el camino azul, reflejado por \. La secuencia "&(mueve el MP hacia atrás y hacia la izquierda (hacia A ), copia el valor de IN a A y lo disminuye.

El IP a continuación, sale de un lado del hexágono y entra de nuevo en el otro lado (en el camino verde). Ejecuta '+que mueve el MP a B y copia lo que había en una . <redirige la IP a Occidente.

Factorial:

Calculo el factorial de una manera específica, por lo que la cuadratura es fácil. Almaceno n-1!en B y C de la siguiente manera.

Factorial

El puntero de instrucciones comienza en el camino azul, en dirección Este.

='invierte la dirección de la MP y se mueve hacia atrás para C . Esto es equivalente a {=tener el lugar =donde fue útil más adelante.

&{copia el valor de A a C , entonces se mueve el MP de nuevo a una . El IP a continuación, sigue el camino verde, sin hacer nada, antes de llegar al camino rojo, golpear \y yendo hacia el camino de naranja.

Con (>, decrementamos A y redirigimos la IP Este. A continuación se realiza un rama: <. Para A positivo , continuamos por el camino naranja. De lo contrario, la IP se dirige hacia el noreste.

'*mueve el MP a B y almacena A * C en B . Aquí es (n-1)*(n-2)donde estaba la entrada inicial n. La IP luego vuelve a entrar en el bucle inicial y continúa disminuyendo y multiplicándose hasta que A llega 0. (informática n-1!)

NB : en los siguientes bucles, &almacena el valor de B en C , ya que C tiene un valor positivo almacenado en él ahora. Esto es crucial para la computación factorial.

Salida:

Salida

Cuando A alcanza 0. La rama dirige la IP a lo largo del camino azul.

=*invierte la MP y almacena el valor de B * C en A . Luego, la IP sale del hexágono y vuelve a entrar en el camino verde; ejecutar "%. Esto mueve el MP a OUT y calcula A mod IN , o (n-1!)² mod n.

Lo siguiente {"actúa como no operativo, ya que se cancelan mutuamente. !imprime la salida final y *+'(se ejecutan antes de la terminación: @.

Después de la ejecución, (con una entrada de 5) la memoria se ve así:

Memoria2

Las bellas imágenes del flujo de control se realizaron con el Hexagony Coloror de Timwi .

Gracias a Martin Ender por generar todas las imágenes, ya que no pude hacerlo en mi PC.

H.PWiz
fuente
¿Qué estás usando para estos diagramas de memoria? He visto IDE Esotérico pero no pude hacerlo funcionar ...
NieDzejkob
@NieDzejkob, es mejor que le preguntes a Martin en el chat, ya que él los hizo para mí de todos modos.
H.PWiz
@NieDzejkob Sí, el diagrama de memoria se puede exportar desde EsoIDE. chat.stackexchange.com/rooms/27364/… si quieres chatear sobre esto un poco más.
Martin Ender
34

Mornington Crescent , 2448 bytes

Estamos de vuelta en 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 fue muy amable al implementar las estaciones de control de flujo Templey Angelen IDE esotérico , así como también agregar entradas y análisis de enteros a la especificación del lenguaje.

Este es probablemente mejor golf que el "¡Hola, mundo!", Porque esta vez escribí un script de CJam para ayudarme a encontrar el camino más corto entre dos estaciones. Si desea usarlo (aunque no sé por qué alguien querría ...), puede usar el intérprete en línea . Pega este código:

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

Aquí las dos primeras líneas son las estaciones que desea verificar. Además, pegue el contenido de este pastebin en la ventana de entrada.

La salida le mostrará qué líneas están disponibles en las dos estaciones, y luego una lista de todas las estaciones que conectan las dos, ordenadas por la longitud de los nombres de las estaciones. Los muestra a todos, porque a veces es mejor usar un nombre más largo, ya sea porque permite una línea más corta o porque la estación es especial (como Bank o Temple), por lo que desea evitarlo. Hay algunos casos extremos en los que dos estaciones no están conectadas por ninguna otra estación (en particular, las líneas Metropolitana y Distrital nunca se cruzan), en cuyo caso tendrá que descubrir otra cosa. ;)

En cuanto al código MC real, se basa en el enfoque factorial cuadrado como muchas otras respuestas porque MC tiene multiplicación, división y módulo. Además, pensé que un solo bucle sería conveniente.

Un problema es que los bucles son bucles do-while, y la disminución y el incremento son caros, por lo que no puedo calcular fácilmente (n-1)!(para n > 0). En cambio, estoy computando n!y luego divido por nal final. Estoy seguro de que hay una mejor solución para esto.

Cuando comencé a escribir esto, pensé que almacenar -1en Hammersmith sería una buena idea para poder disminuirlo más barato, pero al final esto puede haber costado más de lo que ahorró. Si encuentro la paciencia para rehacer esto, podría intentar simplemente mantener un -1recorrido en Upminster para poder usar Hammersmith para algo más útil.

Martin Ender
fuente
10
¿Londres está completo?
Rohan Jhunjhunwala
1
@RohanJhunjhunwala probablemente
Martin Ender
¡Guauu! Me encanta ver preguntas bien pensadas. Especialmente me encanta ver preguntas donde tienes que escribir un programa para escribir un programa.
Rohan Jhunjhunwala
27

Brachylog (V2), 1 byte

ṗ

Pruébalo en línea!

Brachylog (V1), 2 bytes

#pags

Esto utiliza el predicado incorporado #p - Prime, que restringe su entrada para ser un número primo.

Brachylog es mi intento de hacer una versión de Prolog de Code Golf, que es un lenguaje de golf de código declarativo que utiliza el seguimiento y la unificación.

Solución alternativa sin incorporado: 14 bytes

ybbrb'(e:?r%0)

Aquí hay un desglose del código anterior:

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
)
Fatalizar
fuente
1
Es posible que también desee editar la versión Brachylog 2 de esto en la publicación, ahora que la sintaxis es un byte más corta.
1
@ ais523 Cierto, hecho.
Fatalize
¿La respuesta de Brachylog 2 es posterior al desafío?
Scott Milner
1
@ScottMilner Sí, pero esto está explícitamente permitido en este desafío: "A diferencia de nuestras reglas habituales, siéntase libre de usar un idioma (o versión de idioma) incluso si es más nuevo que este desafío"
Fatalize
26

Haskell, 49 bytes

Usando el corolario de xnor al teorema de Wilson :

main=do n<-readLn;print$mod(product[1..n-1]^2)n>0
Lynn
fuente
¿No sería más corto de hacer main=interact$\n-> ...?
John Dvorak
2
Contraintuitivamente, no! Tenga en cuenta que necesitaría interact...readallí en algún lugar, lo que lo hace mucho más largo que solo readLn. A menudo, la donotación puede ser más concisa de lo que cabría esperar, especialmente cuando la alternativa es una lambda.
Lynn
24

Laberinto , 29 bytes

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

Lee un entero de STDIN y las salidas ((n-1)!)^2 mod n. El teorema de Wilson es bastante útil para este desafío.

El programa comienza en la esquina superior izquierda, comenzando con el 1cual multiplica la parte superior de la pila por 10 y agrega 1. Esta es la forma en que Labyrinth construye grandes números, pero dado que las pilas de Labyrinth están llenas de ceros, el efecto final es como si nosotros solo presioné un 1.

?luego lee nde STDIN y lo :duplica. }desplaza na la pila auxiliar, que se utilizará al final del módulo. (luego disminuye n, y estamos listos para comenzar a calcular el factorial al cuadrado.

Nuestro segundo :(duplicado) está en un cruce, y aquí entran en juego las características de flujo de control de Labyrinth. En un cruce después de que se ejecuta una instrucción, si la parte superior de la pila es positiva, giramos a la derecha, para negativo giramos a la izquierda y para cero seguimos recto. Si intentas girar pero chocas contra una pared, Labyrinth te hace girar en la otra dirección.

Porque n = 1, dado que la parte superior de la pila está ndisminuida, o 0, seguimos adelante. Luego llegamos a un no-op 'seguido de otra disminución (que nos pone en -1. Esto es negativo, por lo que giramos a la izquierda, ejecutando +plus ( -1 + 0 = -1), {para nvolver de la pila auxiliar a main y %modulo ( -1 % 1 = 0). Luego salimos con !y terminamos con @.

Para n > 1, en el segundo :giramos a la derecha. Luego cambiamos }nuestro contador de bucle copiado a la pila auxiliar, duplicamos :y multiplicamos dos veces **, antes de volver a cambiar el contador {y disminuirlo (. Si seguimos siendo positivos, intentamos girar a la derecha pero no podemos, por lo que Labyrinth nos hace girar a la izquierda, continuando el ciclo. De lo contrario, la parte superior de la pila es nuestro contador de bucle que se ha reducido a 0, que +agregamos a nuestro calculado ((n-1)!)^2. Finalmente, nretrocedemos con {entonces módulo %, salida !y terminamos @.

Dije que 'es un no-op, pero también se puede usar para depurar. ¡Corre con la -dbandera para ver el estado de la pila cada vez que 'se pasa por alto!

Sp3000
fuente
2
Cuadrar el factorial es un truco realmente genial :)
Lynn
@Mauris Gracias! Sin embargo, necesito dar crédito donde es debido: vi por primera vez el truco utilizado por xnor aquí
Sp3000 el
55
¡Yay, la primera respuesta del Laberinto no escrita por mí! :)
Martin Ender
24

Bash + GNU utilidades, 16

  • 4 bytes guardados gracias a @Dennis

  • 2 bytes guardados gracias a @Lekensteyn

factor|awk NF==2

La entrada es una línea tomada de STDIN. La salida es una cadena vacía para falsey y una cadena no vacía para verdadero. P.ej:

$ ./pr.sh <<< 1
$ ./pr.sh <<< 2
2: 2
$ ./pr.sh <<< 3
3: 3
$ ./pr.sh <<< 4
$
Trauma digital
fuente
2
Genial, aprendí sobre otro coreutil. Puedes quitar dos caracteres contando el número de campos:factor|awk NF==2
Lekensteyn
@Lekensteyn - gracias - por alguna razón me perdí tu comentario antes :)
Digital Trauma
Iba a publicar algo similar, solo por más tiempo y sin AWK. Bien hecho.
David Conrad
21

Java, 126 121 bytes

Supongo que necesitamos una respuesta Java para el marcador ... así que aquí hay un simple ciclo de división de prueba:

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

Como es habitual en Java, el requisito de "programa completo" lo hace mucho más grande de lo que sería si fuera una función, debido principalmente a la mainfirma.

En forma expandida:

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

Editar: arreglado y revisado por Peter en los comentarios. ¡Gracias!

Geobits
fuente
Buggy: informa que 1es primo. De lo contrario, habría un ahorro de 4 caracteres al eliminar py decirfor(;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);}}funciona
Peter Taylor
66
cambiar la línea 3 a 'long i = 2, n = Long.valueOf (a [0]); `no produce cambios en la longitud, sino un rango más amplio de entradas válidas.
James K Polk
44
En lugar de .valueOfusted, puede usar new, como en new Short(a[0]), o new Long(a[0]), que es un poco más corto.
ECS
3
Puede guardar 4 bytes utilizando una interfaz y soltando el publicmodificador.
RamenChef
18

Cerebro-Flak , 112 108 bytes

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

Pruébalo en línea!

Cómo funciona

Inicialmente, la primera pila contendrá un número entero positivo n , la segunda pila estará vacía.

Comenzamos decrementando n de la siguiente manera.

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

n = 1

Si n = 1 es cero, el ciclo while

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

se omite por completo. Finalmente, se ejecuta el código restante.

<>    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 no es cero, ingresamos al ciclo que n = 1 omite. No es un bucle "real"; el código solo se ejecuta una vez. Logra lo siguiente.

{                   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 se calcula utilizando el algoritmo de módulo de 42 bytes de la respuesta de mi prueba de divisibilidad .

Finalmente, interpretamos los resultados para determinar la originalidad 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
fuente
2
No necesita hacer estallar el último 0 en la pila, ya que el verdadero 1 en la parte superior es suficiente; puede guardar dos bytes de esa manera eliminando el último {}.
Steven H.
1
Hm, estoy desgarrado. Por un lado, la pregunta dice que la salida debe consistir únicamente en un valor verdadero o falso y 1 0son dos valores. Por otro lado, aceptaríamos matrices siempre y cuando el lenguaje las considere verdaderas o falsas y múltiples elementos de la pila es lo más cercano que Brain-Flak tiene a las matrices. Podría valer la pena llevar esto a meta.
Dennis
He verificado con el creador de Brain-Flak que 1 0es verdad. chat.stackexchange.com/transcript/message/32746241#32746241
Steven H.
3
Meta discusión relevante: Verdad en Brain-Flak y lenguajes similares basados ​​en pila
Dennis
17

R, 37 29 bytes

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

Utiliza la división de prueba. scan()lee un número entero de STDIN y cat()escribe en STDOUT.

Generamos un vector de longitud que nconsiste en los enteros 1 a nmódulo n. Probamos si cada uno es 0 al negar ( !), que devuelve un valor lógico que es verdadero cuando el número es 0 y falso cuando es mayor que 0. La suma de un vector lógico es el número de elementos verdaderos, y para los números primos esperamos los únicos módulos distintos de cero son 1 y n, por lo tanto, esperamos que la suma sea 2.

¡Guardado 8 bytes gracias a flodel!

Alex A.
fuente
Con f=function(x)sum(!x%%1:x)==2usted puede hacerlo en 28 bytes.
Mutador
2
@ AndréMuta Para este desafío, todas las presentaciones deben ser programas completos en lugar de solo funciones. Gracias por la sugerencia sin embargo.
Alex A.
17

TI-BASIC, 12 bytes

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

Muy claro. randIntNoRep(da una permutación aleatoria de todos los enteros de 1 a Ans.

Esto dobla un poco las reglas; porque las listas en TI-BASIC están limitadas a 999 elementos que interpreté

suponga que la entrada puede almacenarse en su tipo de datos

lo que significa que se puede suponer que todos los tipos de datos acomodan la entrada. OP está de acuerdo con esta interpretación.

Una solución de 17 bytes que realmente funciona hasta 10 ^ 12 más o menos:

2=Σ(not(fPart(Ans/A)),A,1,Ans
lirtosiast
fuente
@toothbrush TI-BASIC es un lenguaje tokenizado , por lo que cada token aquí es un byte, excepto el randIntNoRep(que es dos.
lirtosiast
+1 Ah, nunca había visto TL-BASIC antes. Gracias por hacérmelo saber
Cepillo de dientes
1
Aunque, es un poco injusto, ¿no es así? Debería escribir un lenguaje de golf que requiera solo 1-4 bytes (el ID de la pregunta), y luego los parámetros. Escogerá la respuesta superior en un idioma que comprenda, la ejecutará (pasando cualquier parámetro) y devolverá el resultado ... Me pregunto si eso está rompiendo las reglas. :-)
Cepillo de dientes
@toothbrush En defensa de TI-BASIC: para el intérprete, no es más injusto que los comandos de un solo carácter de Pyth y CJam, y TI-BASIC es más legible.
lirtosiast
1
Cierto. No me gustan esos tipos de idiomas, ya que las soluciones en casi todos los demás idiomas son más largas ... ¡aunque recientemente vencí a CJam con VB6 ! : -]
Cepillo de dientes
15

PARI / GP, 21 bytes

print(isprime(input))

Funciona para entradas ridículamente grandes, porque este tipo de cosas es para lo que PARI / GP está hecho.

Lynn
fuente
66
isprimehace una prueba de primalidad APR-CL, por lo que se ralentiza bastante a medida que las entradas se hacen muy grandes. ispseudoprime(input)realiza una prueba principal probable AES BPSW, que será mucho más rápida para más de 100 dígitos. Todavía no se conocen contraejemplos después de 35 años. La versión 2.1 y anterior de Pari, anterior a 2002, usa un método diferente que puede dar resultados falsos fácilmente, pero nadie debería estar usando eso.
DanaJ
15

TI-BASIC, 24 bytes

Tenga en cuenta que los programas TI-Basic usan un sistema de tokens, por lo que contar caracteres no devuelve el valor de byte real del programa.

Vota la respuesta de Thomas Kwa , es superior.

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

Muestra:

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

Ahora vuelve 0si no es primo, o 1si lo es.

Zenohm
fuente
3
¿No es la raíz cuadrada solo una optimización que realmente no necesita para que el programa sea correcto?
Martin Ender
¿Por qué necesitarías dividir por dos?
Geobits
Siempre me encantan las respuestas de TI-BASIC.
Grant Miller
15

Apilar gatos , 62 + 4 = 66 bytes

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

Debe ejecutarse con los -lnindicadores de la línea de comandos (por lo tanto, +4 bytes). Imprime 0para números compuestos y 1para números primos.

Pruébalo en línea!

Creo que este es el primer programa no trivial de Stack Cats.

Explicación

Una introducción rápida a Stack Cats:

  • Stack Cats opera en una cinta infinita de pilas, con una cabeza de cinta apuntando a una pila actual. Cada pila se llena inicialmente con una cantidad infinita de ceros. En general, ignoraré estos ceros en mi redacción, así que cuando digo "la parte inferior de la pila" me refiero al valor más bajo que no sea cero y si digo "la pila está vacía" me refiero a que solo hay ceros en ella.
  • Antes de que comience el programa, -1se inserta a en la pila inicial, y luego se empuja toda la entrada por encima de eso. En este caso, debido a la -nbandera, la entrada se lee como un entero decimal.
  • Al final del programa, la pila actual se usa para la salida. Si hay una -1en la parte inferior, se ignorará. Nuevamente, debido a la -nbandera, los valores de la pila simplemente se imprimen como enteros decimales separados por salto de línea.
  • Stack Cats es un lenguaje de programa reversible: cada pieza de código se puede deshacer (sin que Stack Cats realice un seguimiento de un historial explícito). Más específicamente, para revertir cualquier pieza de código, simplemente lo refleja, por ejemplo, se <<(\-_)convierte en (_-/)>>. Este objetivo de diseño impone restricciones bastante severas sobre qué tipos de operadores y construcciones de flujo de control existen en el lenguaje, y qué tipo de funciones puede calcular en el estado de la memoria global.

  • Para colmo, cada programa de Stack Cats tiene que ser auto-simétrico. Puede notar que este no es el caso para el código fuente anterior. Para eso está la -lbandera: refleja implícitamente el código a la izquierda, utilizando el primer carácter para el centro. Por lo tanto, el programa real es:

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

La programación efectiva con todo el código es altamente no trivial y poco intuitiva y todavía no se ha dado cuenta de cómo un humano puede hacerlo. Bruscamente forzamos ese programa para tareas más simples, pero no hubiéramos podido acercarnos a eso a mano. Afortunadamente, hemos encontrado un patrón básico que le permite ignorar la mitad del programa. Si bien esto es ciertamente subóptimo, actualmente es la única forma conocida de programar efectivamente en Stack Cats.

Entonces, en esta respuesta, la plantilla de dicho patrón es la siguiente (hay alguna variabilidad en cómo se ejecuta):

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

Cuando se inicia el programa, la cinta de pila se ve así (por entrada 4, por ejemplo):

     4    
... -1 ...
     0
     ^

Se [mueve la parte superior de la pila hacia la izquierda (y la cabeza de la cinta): a esto le llamamos "empujar". Y se <mueve la cabeza de la cinta sola. Entonces, después de los dos primeros comandos, tenemos esta situación:

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

Ahora (...)es un bucle que se puede usar con bastante facilidad como condicional: el bucle se ingresa y se deja solo cuando la parte superior de la pila actual es positiva. Como actualmente es cero, omitimos la primera mitad del programa. Ahora el comando central es *. Esto es simplemente XOR 1, es decir, alterna el bit menos significativo de la parte superior de la pila, y en este caso convierte el 0en 1:

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

Ahora nos encontramos con la imagen especular de la (...). Esta vez la parte superior de la pila es positivo y nos haga entrar en el código. Antes de analizar lo que sucede dentro de los paréntesis, permítanme explicar cómo terminaremos al final: queremos asegurarnos de que al final de este bloque, tengamos el cabezal de la cinta en un valor positivo nuevamente (para que el bucle termina después de una única iteración y se utiliza simplemente como un condicional lineal), que la pila a la derecha mantiene la salida y que el derecho pila de que tiene una -1. Si ese es el caso, dejamos el ciclo, nos >movemos hacia el valor de salida y lo ]empujamos hacia adentro -1para que tengamos una pila limpia para la salida.

Eso es eso. Ahora dentro de los paréntesis podemos hacer lo que queramos para verificar la primalidad siempre y cuando nos aseguremos de configurar las cosas como se describe en el párrafo anterior al final (que puede hacerse fácilmente presionando y moviendo la cabeza de la cinta). Primero intenté resolver el problema con el teorema de Wilson, pero terminé con más de 100 bytes, porque el cálculo factorial al cuadrado es bastante costoso en Stack Cats (al menos no he encontrado un camino corto). Así que fui con la división de prueba y eso resultó mucho más simple. Veamos el primer bit lineal:

>:^]

Ya has visto dos de esos comandos. Además, :intercambia los dos valores superiores de la pila actual y ^XOR el segundo valor en el valor superior. Esto hace :^un patrón común para duplicar un valor en una pila vacía (sacamos un cero encima del valor y luego convertimos el cero en 0 XOR x = x). Luego de esto, la sección de nuestra cinta se ve así:

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

El algoritmo de división de prueba que he implementado no funciona para la entrada 1, por lo que deberíamos omitir el código en ese caso. Podemos asignar fácilmente 1a 0y todo lo demás a valores positivos con *, por lo que aquí es cómo lo hacemos:

*(*...)

Es decir, nos convertimos 1en 0, omitimos una gran parte del código si lo conseguimos 0, pero por dentro lo deshacemos inmediatamente *para recuperar nuestro valor de entrada. Solo necesitamos asegurarnos nuevamente de que terminamos con un valor positivo al final de los paréntesis para que no comiencen a repetirse. Dentro del condicional, movemos una pila hacia la derecha con >y luego iniciamos el ciclo principal de división de prueba:

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

Las llaves (en lugar de paréntesis) definen un tipo diferente de bucle: es un bucle do-while, lo que significa que siempre se ejecuta al menos una iteración. La otra diferencia es la condición de terminación: al ingresar al bucle, Stack Cat recuerda el valor superior de la pila actual ( 0en nuestro caso). El bucle se ejecutará hasta que este mismo valor se vuelva a ver al final de una iteración. Esto es conveniente para nosotros: en cada iteración simplemente calculamos el resto del siguiente divisor potencial y lo movemos a esta pila en la que estamos comenzando el ciclo. Cuando encontramos un divisor, el resto es 0y el ciclo se detiene. Intentaremos los divisores comenzando en n-1y luego los disminuiremos a 1. Eso significa a) sabemos que esto terminará cuando lleguemos1a más tardar y b) podemos determinar si el número es primo o no inspeccionando el último divisor que probamos (si es 1, es primo, de lo contrario no lo es).

Hagámoslo. Hay una sección lineal corta al principio:

<-!<:^>[:

Ya sabes lo que la mayoría de esas cosas hacen ahora. Los nuevos comandos son -y !. Stack Cats no tiene operadores de incremento o decremento. Sin embargo, tiene -(negación, es decir, multiplicar por -1) y !(NO a nivel de bit, es decir, multiplicar por -1y disminuir). Estos se pueden combinar en un incremento !-o decremento -!. Por lo tanto, disminuimos la copia nen la parte superior -1, luego hacemos otra copia nen la pila a la izquierda, luego buscamos el nuevo divisor de prueba y lo colocamos debajo n. Entonces, en la primera iteración, obtenemos esto:

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

En iteraciones posteriores, 3se reemplazará con el siguiente divisor de prueba y así sucesivamente (mientras que las dos copias nsiempre tendrán el mismo valor en este punto).

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

Este es el cálculo del módulo. Como los bucles terminan en valores positivos, la idea es comenzar desde -ny agregarle repetidamente el divisor de prueba dhasta obtener un valor positivo. Una vez que lo hacemos, restamos el resultado dy esto nos da el resto. La parte difícil aquí es que no podemos simplemente poner una -nparte superior de la pila y comenzar un ciclo que agrega d: si la parte superior de la pila es negativa, no se ingresará el ciclo. Tales son las limitaciones de un lenguaje de programación reversible.

Entonces, para evitar este problema, comenzamos con la nparte superior de la pila, pero lo negamos solo en la primera iteración. De nuevo, eso suena más simple de lo que parece ser ...

(-<)

Cuando la parte superior de la pila es positiva (es decir, solo en la primera iteración), la negamos con -. Sin embargo, no podemos hacerlo (-)porque no estaríamos dejando el ciclo hasta que -se aplicara dos veces. Así que movemos una celda hacia la izquierda <porque sabemos que hay un valor positivo allí (el 1). Bien, ahora hemos negado de manera confiable nen la primera iteración. Pero tenemos un nuevo problema: la cabeza de la cinta ahora está en una posición diferente en la primera iteración que en cualquier otra. Necesitamos consolidar esto antes de seguir adelante. El siguiente <mueve la cabeza de la cinta hacia la izquierda. La situación en la primera iteración:

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

Y en la segunda iteración (recuerde que hemos agregado duna vez -nahora):

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

El siguiente condicional fusiona estos caminos nuevamente:

(<!-)

En la primera iteración, el cabezal de la cinta apunta a cero, por lo que se omite por completo. Sin embargo, en otras iteraciones, el cabezal de la cinta apunta a uno, así que ejecutamos esto, nos movemos hacia la izquierda e incrementamos la celda allí. Como sabemos que la celda comienza desde cero, ahora siempre será positiva para que podamos abandonar el ciclo. Esto garantiza que siempre terminemos dos pilas a la izquierda de la pila principal y que ahora podamos retroceder >>. Luego, al final del ciclo módulo lo hacemos -_. Usted ya sabe -. _es restar lo que ^es para XOR: si la parte superior de la pila es ay el valor debajo es breemplazado apor b-a. Desde la primera vez negada asin embargo, -_reemplaza acon b+a, añadiendo asíd en nuestro total acumulado.

Una vez que finaliza el ciclo (hemos alcanzado un valor positivo), la cinta se ve así:

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

El valor más a la izquierda podría ser cualquier número positivo. De hecho, es el número de iteraciones menos uno. Hay otro bit lineal corto ahora:

_<<]>:]<]]

Como dije antes, necesitamos restar el resultado dpara obtener el resto real ( 3-2 = 1 = 4 % 3), por lo que solo lo hacemos _una vez más. Luego, necesitamos limpiar la pila que hemos estado incrementando a la izquierda: cuando probamos el siguiente divisor, debe ser cero nuevamente, para que la primera iteración funcione. Entonces nos movemos allí y empujamos ese valor positivo en la otra pila auxiliar con <<]y luego volvemos a nuestra pila operativa con otra >. Nos detenemos dcon :y vuelva a insertarla en el -1con ]y luego nos movemos hacia el resto de nuestra pila condicional con <]]. Ese es el final del ciclo de división de prueba: esto continúa hasta que obtengamos un resto cero, en cuyo caso la pila a la izquierda contienenEl mayor divisor (aparte de n).

Después de que finaliza el ciclo, hay justo *<antes de que unamos 1nuevamente las rutas con la entrada . El *simplemente se vuelve el cero en una 1, lo que vamos a necesitar un poco, y luego se pasa al divisor con <(por lo que estamos en la misma pila que para la entrada 1).

En este punto, ayuda a comparar tres tipos diferentes de entradas. Primero, el caso especial n = 1donde no hemos hecho nada de eso de la división de prueba:

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

Luego, nuestro ejemplo anterior n = 4, un número compuesto:

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

Y finalmente, n = 3un número primo:

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

Entonces, para los números primos, tenemos un 1en esta pila, y para los números compuestos tenemos 0un número positivo o mayor que 2. Nos dirigimos esta situación en el 0o 1que necesitamos con la siguiente pieza final de código:

]*(:)*=<*

]simplemente empuja este valor a la derecha. A continuación, *se utiliza para simplificar la situación condicionada en gran medida: alternando el bit menos significativo, nos volvemos 1(primer) en 0, 0(compuesto) en el valor positivo 1, y todos los demás valores positivos seguirán siendo positivo. Ahora solo necesitamos distinguir entre 0y positivo. Ahí es donde usamos otro (:). Si la parte superior de la pila es 0(y la entrada fue un primo), esto simplemente se omite. Pero si la parte superior de la pila es positiva (y la entrada era un número compuesto), esto se intercambia con el 1, de modo que ahora tenemos 0para compuesto y1para primos: solo dos valores distintos. Por supuesto, son lo opuesto a lo que queremos generar, pero eso se soluciona fácilmente con otro *.

Ahora todo lo que queda es restaurar el patrón de pilas esperado por nuestro marco circundante: cabeza de cinta en un valor positivo, resultado en la parte superior de la pila a la derecha, y un solo -1en la pila a la derecha de eso . Esto es para lo que =<*sirve. =intercambia la parte superior de las dos pilas adyacentes, moviendo así -1a la derecha del resultado, por ejemplo, para ingresar 4nuevamente:

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

Luego nos movemos a la izquierda con <y convertimos ese cero en uno con *. Y eso es eso.

Si desea profundizar en cómo funciona el programa, puede utilizar las opciones de depuración. Agregue el -dindicador e insértelo "donde desee ver el estado actual de la memoria, por ejemplo , de esta manera , o use el -Dindicador para obtener un seguimiento completo de todo el programa . Alternativamente, puede usar EsotericIDE de Timwi, que incluye un intérprete de Stack Cats con un depurador paso a paso.

Martin Ender
fuente
3
>:^]debería ser el logotipo oficial de Stack Cats
Alex A.
14

Haskell, 54 bytes

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

No hay mucho que explicar.

nimi
fuente
1
Se puede lograr el mismo puntaje (aunque de manera muy ineficiente) sin bibliotecas externas, utilizando el teorema de Wilson:main=do n<-readLn;print$n>1&&mod(product[1..n-1]+1)n<1
Lynn
99
Incluso podemos hacer más corto: main=do n<-readLn;print$mod(product[1..n-1]^2)n>0es de 49 bytes.
Lynn
44
@Mauris: Bien. Por favor publíquelo como una respuesta separada.
nimi
14

Rubí, 15 + 8 = 23 bytes

p$_.to_i.prime?

Ejecución de muestra:

bash-4.3$ ruby -rprime -ne 'p$_.to_i.prime?' <<< 2015
false
hombre trabajando
fuente
Jeje, sabía que habría un lugar en Ruby en alguna parte, pero no me molesté en buscarlo, así que respondí en C. +1.
Level River St
@steveverrill, lo sabía porque fue una gran ayuda para el Proyecto Euler.
manatwork
14

JavaScript, 39 36 bytes

Guardado 3 bytes gracias a ETHproductions:

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

Muestra verdadero para un primo, falso de lo contrario.

El bucle for prueba cada número i desde n-1 hasta que yo sea ​​un divisor. Si el primer divisor encontrado es 1, entonces es un número primo.

Solución anterior (39 bytes):

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

Cómo quedó una prueba innecesaria:

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

Solo publiqué la solución de 39 bytes porque la mejor respuesta de JavaScript ya era de 40 bytes.

Hedi
fuente
2
¡Bienvenido a Programming Puzzles & Code Golf!
Dennis
2
¡Gran respuesta! En &&irealidad, no hace nada en este programa, por lo que puede eliminarlo.
ETHproductions
n>1sin embargo, debe agregarse a la condición final, si no desea 1ser primo.
Titus
1
@Titus Si la entrada es 1el bucle for lo hará n%--iuna vez: 1%0vuelve NaNy detiene el bucle. Cuando alertse llama iya es igual a 0lo que 1==idevuelve false.
Hedi
2
i <2 (y algo de texto)
Scheintod
13

Caracoles, 122

La entrada debe darse en unario. Los dígitos pueden ser cualquier combinación de caracteres, excepto las nuevas líneas.

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

En este lenguaje de coincidencia de patrones 2D, el estado del programa consiste únicamente en la ubicación actual de la cuadrícula, el conjunto de celdas que se han emparejado y la posición en el código del patrón. También es ilegal viajar a un cuadrado coincidente. Es complicado, pero es posible almacenar y recuperar información. La restricción contra viajar a una celda coincidente se puede superar mediante retroceso, teletransportación ( t) y aserciones ( =, !) que dejan la cuadrícula sin modificar después de completarse.

Factorización de 25

La factorización para un número compuesto impar comienza marcando un conjunto de celdas mutuamente no adyacentes (azul en el diagrama). Luego, de cada celda amarilla, el programa verifica que haya un número igual de celdas no azules a cada lado de la celda azul adyacente al desplazarse de un lado a otro entre los dos lados. El diagrama muestra este patrón para una de las cuatro celdas amarillas que deben verificarse.

Código anotado:

^                         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
fuente
13

C, 67 bytes

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

Imprime !1(un valor de falsey, según la definición de Peter Taylor ) 0 si (n-1)!^2 == 0 (mod n), y1 otra manera.

EDITAR : después de una discusión en el chat, puts("!1"+p%n)parece ser considerado un poco engañoso, así que lo he reemplazado. El resultado es un byte más largo.

EDITAR : Corregido para entradas grandes.

Soluciones más cortas

56 bytes : como se recomienda en los comentarios de pawel.boczarski, podría tomar la entrada en unario leyendo el número de argumentos de la línea de comando:

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

invocando el programa como

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

51 bytes : si permite la "salida" mediante códigos de retorno:

p=1,n;main(i){for(n=--i;--i;p=p*i*i%n);return p%n;}
Lynn
fuente
Su solución podría acortarse utilizando una representación unaria (número de argumentos de línea de comandos), como en mi solución publicada. Podría reducir algunos bytes en la llamada scanf.
pawel.boczarski
puts("!1"+p%n)¿Cómo podrías hacer a+bpara los char*valores?
Erik the Outgolfer
Si la cadena "!1"comienza en la dirección a, entonces a+1encontrará la cadena "1".
Lynn
@Lynn Oh, pensé que era para la concatenación (sí, mejor dejar que a strcat(const char*,const char*).)
Erik el Outgolfer
¿Podrías cambiarte p=p*i*i%nap*=i*i%n
Albert Renshaw el
12

Python 3, 59 bytes

Ahora usa en input()lugar de argumentos de línea de comando. Gracias a @Beta Decay

n=int(input())
print([i for i in range(1,n)if n%i==0]==[1])
uno20001
fuente
Tomar entrada usando input()sería mucho más corto
Beta Decay
Gracias, ya he escrito con el uso de input (), pero olvidé actualizar mi respuesta. ¡Gracias de nuevo!
uno20001
44
52 bytes: n=m=int(input()),print(all(n%m for m in range(2,n)))
John Lyon
1
En serio. ¿Gasta 25 personajes adicionales para una aceleración cuadrática cojo? Aquí odiamos los bytes . Pasamos cada hora, minuto y segundo de nuestras vidas deshaciéndonos del decimonoveno byte. (Es broma. Pero no hacemos optimizaciones de tiempo que aumenten la duración del programa.)
CalculatorFeline
2
Usar en su n%i<1lugar.
Erik the Outgolfer
12

APL, 40 13 bytes

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

Sala de primera instancia con el mismo algoritmo que mi R respuesta . Asignamos xa la entrada de STDIN ( ⎕) y obtenemos el resto para xdividido por cada entero de 1 a x. Cada resto se compara con 0, lo que nos da un vector de unos y ceros que indica qué números enteros se dividen x. Esto se suma usando +/para obtener el número de divisores. Si este número es exactamente 2, esto significa que los únicos divisores son 1 y x, por lo tanto, xes primo.

Alex A.
fuente
12

Metaprogramación de plantilla C ++. 166 131 119 bytes.

El código se compila si la constante es primo y no se compila si es compuesto o 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];

(todas las líneas nuevas, excepto la final, se eliminan en la versión "real").

Me imagino que "falla al compilar" es un valor de retorno falso para un lenguaje de metaprogramación. Tenga en cuenta que no se vincula (por lo tanto, si lo alimenta con primos, obtendrá errores de vinculación) como un programa completo de C ++.

El valor a probar es el entero en la última "línea".

ejemplo vivo .

Yakk
fuente