La "rana prima" es un animal extraño que salta entre enteros, hasta que llega el 3 o 19 ...
Su programa debe aceptar un número entero n
como entrada y salida del resultado del algoritmo siguiente ( 3
o 19
).
Para un entero dado n >= 2
:
- Dejar
f
ser la posición de la rana. Inicialmente se establece enn
- if
f = 3
orf = 19
: la rana deja de saltar: detiene el programa y la salidaf
. - si
f
es primo: la rana salta a la posición2×f-1
. Regrese al paso 2. - si
f
es compuesto: dejar qued
seaf
's divisor primo mayor. La rana salta a la posiciónf-d
. Regrese al paso 2.
Ejemplos:
Un ejemplo con n = 5
:
5 > 9 > 6 > 3 stop
El programa debería salir 3
.
Otro ejemplo con n = 23
:
23 > 45 > 40 > 35 > 28 > 21 > 14 > 7 > 13 > 25 > 20 > 15 > 10 > 5 > 9 > 6 > 3 stop
De nuevo, el programa debería salir 3
.
Casos de prueba:
10 => 3
74 => 19
94 => 3
417 => 3
991 => 19
9983 => 19
Puede suponer 1 < n < 1000000
(he comprobado que el programa termina con estos valores).
3
o19
, podríamos cambiar el elemento 2. en el algoritmo para decir que si la rana ha entrado en un bucle (ha encontrado una posición que ha visto antes), entonces deja de saltar y devuelve el más pequeño miembro de ese ciclo.Respuestas:
Python 2 ,
101939290888785 bytesPruébalo en línea!
fuente
while~16&n!=3
Guarda un byte.~16&n-3
incluso funciona!C (gcc),
8765 bytesPruébalo en línea!
Explicación:
Versión portátil (72 bytes):
Pruébalo en línea!
Con nombres de variables más apropiados:
Pruébalo en línea!
fuente
Retina ,
6362 bytesGracias a Neil por guardar 1 byte.
Pruébalo en línea!
Entrada y salida en unario (el conjunto de pruebas usa decimal por conveniencia). Esta solución se vuelve increíblemente lenta para entradas más grandes. El
9983
caso de prueba expira en TIO.Explicación
Debido a esto
{
, ambas etapas del programa simplemente se ejecutan en un bucle hasta que ya no afectan a la cadena. Alternamos entre una etapa de procesamiento de compuestos y una etapa de procesamiento de primos. Eso nos permite evitar un condicional real (que realmente no existe en Retina). Si el valor actual es del tipo incorrecto para la etapa, la etapa simplemente no hace nada.Esto procesa compuestos. Emparejamos un divisor potencial con
(11+)
, pero luego verificamos que no está compuesto con(?<!^\2+(11+))
, por lo que solo consideramos factores primos. Debido a la codicia de+
, esto prioriza el factor más importante. Luego verificamos que este divisor potencial es un divisor real tratando de hacer coincidir el resto de la cadena con repeticiones de la misma(?=\1+$)
. Este divisor simplemente se elimina de la cadena, que es cómo restas algo en unario.Esto procesa primos, excepto 3 y 19 . La anticipación negativa asegura que la entrada no sea compuesta, ni 3 ni 19 . Luego hacemos coincidir un solo
1
y lo reemplazamos con toda la cadena. Esta es una forma unaria de computación n - 1 + n , que por supuesto es 2n-1 .Una vez que tocamos 3 o 19 , ninguna etapa puede coincidir con la cadena y ya no se cambiará.
fuente
1$'
mismo que$_
?Casco , 15 bytes
Pruébalo en línea!
Explicación
fuente
Jalea , 12 bytes
Pruébalo en línea!
Cómo funciona
fuente
Wolfram Language (Mathematica) , 65
6668bytesPruébalo en línea!
Inspirado en la punta . Básicamente, solo recrea el algoritmo.
//.
esRepeatedReplace
y/;
esCondition
. Entonces, el código reemplazarái_
(una sola cantidad) conIf[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]
, hasta que sei!=3&&!=19
evalúeTrue
.Punto de referencia:
fuente
10000000010
maximum number of iterations is 2^16 (= 65536)
#//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]&
05AB1E ,
191817 bytesPruébalo en línea!
Explicación
fuente
<ë
JavaScript (ES6),
737169 bytesCasos de prueba
Mostrar fragmento de código
Formateado y comentado
fuente
57%n
y enn%38
lugar den==3|n==19
. También guardé 1 byte en mi respuesta Java , ¡así que gracias!Jalea ,
2319 bytes-4 bytes de millas . Sin embargo, aún más largo que 05AB1E
Pruébalo en línea!
fuente
Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿
usando un bucle while en su lugar y algunos reordenamientosPython 2 ,
110105103101 bytes-2 bytes gracias a @Lynn
Pruébalo en línea!
Python 2 ,
116112105 bytesPruébalo en línea!
fuente
…n*(n&~16==3)or…
ahorra 2 bytes.MATL ,
2221 bytes¡Gracias a @Giuseppe por eliminar 1 byte!
Pruébalo en línea! O verificar todos los casos de prueba .
Explicación
fuente
Haskell - 154 bytes
Probablemente faltan algunos trucos de golf aquí, este es mi primer intento en Haskell Golf.
fuente
1>0
paraTrue
la mayoría de las veces, pero a menudo puede ser que sea mejor usar una asignación, por ejemploc<-z n
.[x|x<-[b-1,b-2..1],rem b x==0]
También es corto quereverse[x|x<-[1..(b-1)],b
remx==0]
.Neim ,
1716 bytesExplicación:
Pruébalo en línea!
fuente
Números R + ,
10299 bytesPruébalo en línea!
R no es conocido por sus complementos cortos, ¡e incluso los paquetes hacen lo mismo!
fuente
Java 8,
14013513494 bytes-5 bytes que convierten el método recursivo Java 7 a Java 8 lambda con bucle.
-1 byte implícito gracias a la respuesta de JavaScript de @Arnauld cambiando
n!=3&n!=19
yreturn n;
hacia57%n>0
yreturn n%38;
.Creo que debería ser posible de alguna manera combinar los dos bucles y verificar sin
es primo, y obtener su mayor factor primo al mismo tiempo, pero no puedo resolverlo (todavía). Entonces esta será la versión inicial por ahora.-40 enormes bytes gracias a @Nevay, haciendo lo que no pude hacer: combinando los bucles para verificar los primos y el factor primo más grande a la vez.
Explicación:
Pruébelo aquí (se ejecuta incluso
999999
en menos de 1 segundo).fuente
n=>
lugar den->
. Y a veces llamadas en minúsculas / mayúsculas. ;)n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;)t/=m=f;return n%38;}
Bash, 73 bytes
Pruébalo en línea! Modificado ligeramente para trabajar en TIO.
Recursivamente llama a su propio archivo de script utilizando
$0
,que no funciona en TIO porque debe ejecutarse como. Acepta entradas como argumento de línea de comandos../filename.sh
Utiliza el mismo truco de módulo que la respuesta JS de @ Arnauld .
Casos de prueba
fuente
Python 3 , 97 bytes
Pruébalo en línea!
fuente
Pyth , 19 bytes
¡Verifique todos los casos de prueba!
La respuesta de Husk me inspiró a guardar 2 bytes (
,3 19
paraP57
).Como funciona esto
fuente
PowerShell ,
150126 bytesPruébalo en línea! (advertencia: lento para números más grandes)
Método iterativo PowerShell no tiene incorporados factores primos de factorización, por lo que toma prestado el código de mi respuesta en Prime Factors Buddies .
Primero es nuestro
for
bucle. La configuración se establece$n
como el valor de entrada, y el condicional mantiene el ciclo en marcha siempre que57%$n
no sea cero (gracias a Arnauld por ese truco). Dentro del ciclo, primero obtenemos una lista de factores primos de$a
(establecido en$n
). Este es el código prestado de Prime Factors Buddies. Si la entrada$a
ya es primo, esto devolverá solo$a
(importante más adelante). Eso (potencialmente solo$a
) se almacena en$d
.El siguiente es un
if
/else
condicional. Por elif
lado, verificamos si$n
es así-in
$d
. Si es así, eso significa que$n
es primo, así que tomamos$n=2*$n-1
o$n+=$n-1
. De lo contrario, es compuesto, por lo que necesitamos encontrar el factor primo más grande. Eso significa que necesitamos tomar el último[-1]
de$d
y restarlo de$n
con$n-=
. Esto funciona porque estamos haciendo un bucle2
y, por lo tanto, el último elemento$d
ya será el más grande.Una vez que terminamos de hacer un bucle, simplemente colocamos
$n%38
(nuevamente, gracias Arnauld) en la tubería y la salida está implícita.fuente
APL (Dyalog Unicode) ,
1139059 bytesPruébalo en línea!
TIO funciona con valores de hasta ~ 3200. Probado en mi PC para el último caso de prueba. Para probar en TIO, simplemente agregueYa no se aplica, gracias a @ Adám por señalar que mi algoritmo de comprobación de primalidades era realmente malo y me proporcionó un reemplazo; También para el guardado de 23 bytes.f value
al final del código.Editado para arreglar el conteo de bytes.
Cómo funciona
fuente
Axioma, 93 bytes
prueba:
Habría 68 bytes de función
pero para n = 57991 (si mal no recuerdo) sale el espacio reservado de la pila.
fuente
Python 2 , 93 bytes
Puerto de la respuesta de TFeld sin libs externas.
Pruébalo en línea!
fuente