Un número altamente compuesto es un número entero positivo que tiene más divisores que cualquier número entero positivo más pequeño. Esta es la secuencia OEIS A002182 . Sus primeros 20 términos son
1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560
Por ejemplo, 4
está en la secuencia porque tiene 3 divisores (es decir, 1, 2, 4), mientras que 3 solo tiene 2 divisores, 2 también tiene 2 divisores y 1 tiene 1 divisores.
Reto
Dada una entrada entera positiva n , emite el n -ésimo número altamente compuesto o los primeros n números altamente compuestos, a su elección (pero la elección debe ser la misma para cada entrada n ).
Reglas
El programa o función debería funcionar teóricamente para entradas arbitrariamente grandes con tiempo y memoria infinitos, y sin tener en cuenta las limitaciones del tipo de datos. Esencialmente, esto significa que no hay que codificar un número finito de valores.
En la práctica, el programa o función debe ejecutarse en un período de tiempo razonable, digamos menos de 1 minuto, para n hasta 20. La entrada o salida máxima puede estar limitada por el tipo de datos estándar de su idioma (pero nuevamente, el algoritmo debería funcionar teóricamente para números arbitrariamente grandes).
Se permite cualquier formato de entrada y salida razonable, incluido el unario.
Código de golf. Pocos bytes ganan.
fuente
Respuestas:
05AB1E ,
1514 bytesLa entrada en cero indexado. Eso significa que
n = 0
da1
,n = 1
da2
, etc. Código:Explicación:
Calcula n = 19 , que debería dar
7560
en unos 10 segundos.Pruébalo en línea!
Utiliza la codificación CP-1252 .
fuente
Jalea, 15 bytes
Para la entrada n , imprime el primer n números altamente compuestos.
Para n = 20 , lleva menos de dos segundos probarlo en línea.
Cómo funciona
Versión alternativa, 13 bytes (no competitiva)
Si bien el código siguiente funcionó en la última versión de Jelly que precede a este desafío, la implementación
M
fue muy lenta y no cumplió con el límite de tiempo. Esto ha sido arreglado.Pruébalo en línea!
Cómo funciona
fuente
RÆDL€MḢ=µƓ#
(11 bytes), pero tarda 44 minutos en mi máquina ...MATL ,
2624 bytesPruébalo en línea!
El mayor número actual de divisores encontrados se mantiene en el portapapeles K. Los números altamente compuestos (HCN) se guardan directamente en la pila. Un bucle sigue probando candidatos para HCN. Cuando se encuentra uno, se deja en la pila y se actualiza el portapapeles K. El ciclo sale cuando se ha encontrado el número deseado de HCN.
fuente
Perl,
6057 + 1 = 58 bytesRequiere
-n
y el libre-M5.010
|-E
:Cómo funciona:
fuente
JavaScript (ES6) 72
Implementación directa. Tiempo cercano a 20 segundos para la entrada 20
El truco eval podría ahorrar un byte duplicando el tiempo de ejecución
Menos golf
fuente
Pyth,
1716 bytes1 byte gracias a Jakube
Banco de pruebas
Toma un n indexado por 0 y devuelve el enésimo número altamente compuesto.
Explicación:
fuente
Rubí,
706967666462Implementación directa.
fuente
C, 98 bytes
Probarlo aquí .
Sin golf
fuente
Python 3, 97 bytes
Un programa completo que toma la entrada de STDIN e imprime la salida a STDOUT. Esto devuelve el
n
número 1 altamente compuesto indexado.Cómo funciona
Esta es una implementación sencilla. La entrada
n
es el índice numérico altamente compuesto.El programa itera sobre los enteros
i
. Para cada número enteroj
menor quei
,i mod j
se toma; si es así0
,j
debe ser un factor dei
y el contadorc
se incrementa, dando el número de divisores dei
después del bucle.p
es el número más alto anterior de divisores, por lo que sic > p
se ha encontrado un nuevo número altamente compuesto y el contadorq
se incrementa. Una vezq = n
,i
debe ser eln
número altamente compuesto, y esto se imprime.Pruébalo en Ideone
(Esto lleva unos 15 segundos
n = 20
, lo que excede el límite de tiempo para Ideone. Por lo tanto, el ejemplo dado es paran = 18
).fuente
Python 2, 207 bytes
Utiliza el mismo método que Dennis 'Jelly answer. Calcula los primeros 20 términos en
<2
segundos.fuente