Un divisor de un número n es cualquier número que divida uniformemente n , incluidos 1 yn . El número de divisores d (n) es cuántos divisores tiene un número. Aquí está d (n) para la primera pareja n:
n divisors d(n)
1 1 1
2 1, 2 2
3 1, 3 2
4 1, 2, 4 3
5 1, 5 2
6 1, 2, 3, 6 4
Podemos restar repetidamente el número de divisores de un número. Por ejemplo:
16 = 16
16 - d(16) = 16 - 5 = 11
11 - d(11) = 11 - 2 = 9
9 - d( 9) = 9 - 3 = 6
6 - d( 6) = 6 - 4 = 2
2 - d( 2) = 2 - 2 = 0
En este caso, tomó 5 pasos para llegar a 0.
Escriba un programa o función que, dado un número no negativo n, devuelva el número de pasos necesarios para reducirlo a 0 mediante la resta repetida del número de divisores.
Ejemplos:
0, 0
1, 1
6, 2
16, 5
100, 19
100000, 7534
Respuestas:
Jalea,
109 bytes1 byte gracias a Dennis ♦ .
Puerto de mi respuesta en Pyth .
Pruébalo en línea!
Banco de pruebas.
Explicación
fuente
Python, 49 bytes
¡orlp ayudó a salvar un byte! Y Sp3000 salvó dos más. ¡Gracias!
fuente
-~
interiorn%-~k
y eliminando el límite inferior del rango.C, 52 bytes
fuente
Pyth, 10 bytes
Banco de pruebas.
Explicación
fuente
Julia, 31 bytes
Implementación recursiva directa.
fuente
MATL , 14 bytes
Pruébalo en línea!
Explicación
fuente
JavaScript (ES6),
6451 bytesNo me preguntes por qué estaba usando innecesariamente la recursión de cola.
fuente
Java,
14793fuente
n=new Integer(100000)
lugar den=100000
?05AB1E,
1210 bytesCódigo:
Explicación:
Pruébalo en línea
Editar: 2 bytes guardados y un error con la entrada 0 corregida gracias a @Adnan
fuente
[Ð>#Ñg-¼]¾
. Sin embargo, tiene que haber una manera de acortarlo ...D0Q#
parte es después del incremento del contador. El[Ð>#Ñg-¼]¾
código debe trabajar para0
aunque :).R, 50 bytes
Implementación bastante simple. Pruébalo en línea
fuente
Mathcad, [tbd] bytes
El esquema de equivalencia de bytes de Mathcad aún no se ha determinado. Usando una equivalencia aproximada de teclas, el programa usa alrededor de 39 "bytes". Tenga en cuenta que los operadores while y para programación solo requieren una operación de teclado cada uno para ingresar (ctl-] y ctl-shft- #, respectivamente); de hecho, solo se pueden ingresar de esta manera desde el teclado.
Lo que ve es exactamente lo que se anota en una hoja de trabajo de Mathcad. Mathcad evalúa las ecuaciones / programas y coloca la salida en la misma hoja (p. Ej., Después del operador de evaluación '=' o en la gráfica).
fuente
MATL, 13 bytes
Pruébalo en línea
Explicación:
fuente
Mathematica, 35 bytes
Haciendo uso de los buenos viejos
DivisorSigma
. @ MartinBüttner señala las siguientes alternativas:fuente
Hoon ,
9376 bytesSin golf:
Devuelve una función que toma un átomo,
r
. Cree un valor intermedio que contenga todos los dispositivos der
(Haga la lista [1..n], mantenga solo los elementos donde (mod ri) == 0). Sir
es cero, devuelve cero; de lo contrario, devuelve el valor incrementado de recurrencia con r igual r- (divisores de longitud).El código tal como está toma una estúpida cantidad de tiempo para evaluar n = 100.000, completamente porque encontrar los inventores para grandes números hace una lista gigante y mapas sobre él. Memorizar los divisores obtiene la salida correcta para n = 10.000, pero no me molesté en esperar 100.000
fuente
Haskell,
434039 bytesEnfoque recursivo simple. Ejemplo de uso:
g 16
->5
.Editar: @Lynn guardó
34 bytes. ¡Gracias!fuente
g(sum$signum.mod n<$>[1..n])
?min 1
realidad es un byte más corto quesignum
, inclusoPowerShell v2 +,
7467 bytesParece bastante largo en comparación con algunas de las otras respuestas ...
Toma entrada
$n
, entra en unfor
bucle con la condición que$n
es mayor que0
. En cada iteración de bucle establecemos ayudante$a
, luego recorremos cada número desde1
hasta$n
. Cada ciclo interno lo comprobamos contra cada número para ver si es un divisor, y si es así, incrementamos nuestro auxiliar$a
(usando la negación booleana y la conversión implícita a int). Luego, restamos cuántos divisores hemos encontrado$n-=$a
e incrementamos nuestro contador$o++
. Finalmente, sacamos$o
.Lleva mucho tiempo ejecutarlo, ya que es una construcción significativa de bucle for. Por ejemplo, ejecutar
n = 10,000
en mi máquina (1 año de edad Core i5) toma casi 3 minutos.fuente
Raqueta -
126 bytes Hasta 98 bytes91 bytesUna solución extremadamente ingenua: probablemente podría reducirse mucho con un algoritmo decente y algunos trucos de ceceo que no conozcoEditar: explicación por solicitud. Como dije, esta es una solución recursiva extremadamente ingenua y puede ser mucho más corta.
Edición 2: versión de 98 bytes con un algoritmo menos tonto (aunque sigue siendo bastante tonto y puede ser más corto)Explicación:Edición 3: guardado 7 bytes reemplazando
(cdr(build-list x values))
con(build-list x add1)
fuente
> <> , 52 + 2 = 54 bytes
El número de entrada debe estar presente en la pila al inicio del programa, por lo que hay +2 bytes para el
-v
indicador. Pruébalo en línea!4 bytes molestos desperdiciados en problemas de alineación. Bah.
Este funciona construyendo la secuencia de
n
a0
en la pila. Una vez que se ha alcanzado 0, explótelo y supere la longitud de la pila restante.Por cierto, corre a
O(n^2)
tiempo, así que no lo intentarían = 100000
...fuente
-v
es un byte, no dos.> <> , 36 + 3 = 39 bytes
La implementación es relativamente sencilla, siendo cada iteración
sum(n%k>0 for k in range(1,n-1))
. +3 bytes para la-v
bandera, por meta .Pruébalo en línea!
fuente
Ruby, 42 bytes
Hay un error de desbordamiento de pila en el caso de prueba más grande
100000
, así que aquí hay una versión iterativa dentro de 49 bytes . Sin embargo, toma un tiempo, considerando laO(N^2)
complejidad.fuente
Perl 5, 40 bytes
La entrada y salida son como listas del número requerido de copias de
1
.fuente
C #, 63 bytes
fuente
En realidad, 17 bytes
Pruébalo en línea! (nota: el último caso de prueba expira en TIO)
Explicación:
fuente