Un divisor propio es un divisor de un número n , que no es n en sí mismo. Por ejemplo, los divisores propios de 12 son 1, 2, 3, 4 y 6.
Se le dará un número entero x , x ≥ 2, x ≤ 1000 . Su tarea es sumar todos los divisores propios más altos de los enteros de 2 a x (inclusive) (OEIS A280050 ).
Ejemplo (con x = 6
):
Encuentre todos los enteros entre 2 y 6 (inclusive): 2,3,4,5,6.
Obtenga los divisores adecuados de todos ellos y elija los más altos de cada número:
- 2 -> 1
- 3 -> 1
- 4 -> 1, 2
- 5 -> 1
- 6 -> 1, 2, 3 .
Resumiendo los más altos divisores propios:
1 + 1 + 2 + 1 + 3 = 8
.El resultado final es 8.
Casos de prueba
Entrada | Salida ------- + --------- El | 2 | 1 4 | 4 4 6 | 8 8 | 13 15 | 41 37 | 229 100 1690 1000 | 165279
Reglas
Se aplican las lagunas predeterminadas .
Puede tomar entrada y proporcionar salida por cualquier método estándar .
Este es el código de golf , ¡la presentación válida más corta en cada idioma gana! ¡Que te diviertas!
Respuestas:
Oasis , 4 bytes
Código:
Pruébalo en línea!
Explicación:
Versión extendida:
fuente
Casco , 7 bytes
Pruébalo en línea!
Explicación
Husk no tiene una función integrada para calcular los divisores directamente (todavía), por lo que en su lugar estoy usando factorización prima. El divisor propio más grande de un número es el producto de sus factores primos, excepto el más pequeño. Mapeo esta función en el rango de 2 a la entrada, y sumo los resultados.
fuente
Python 2 , 50 bytes
Esto es lento y ni siquiera puede hacer frente a la entrada 15 en TIO.
Pruébalo en línea!
Sin embargo, la memorización ( gracias @ musicman523 ) se puede utilizar para verificar todos los casos de prueba.
Pruébalo en línea!
Versión alternativa, 52 bytes.
A un costo de 2 bytes, podemos elegir si calcular
f(n,k+1)
o non/k+f(n-1)
.Con algunos trucos, esto funciona para todos los casos de prueba, incluso en TIO.
Pruébalo en línea!
fuente
f
es una función pura , puede memorizarla para ejecutar los casos más grandes en TIOJalea , 6 bytes
Pruébalo en línea!
Cómo funciona
fuente
Brachylog , 10 bytes
Pruébalo en línea!
fuente
JavaScript (ES6), 40 bytes
Un número es igual al producto de su divisor propio más alto y su factor primo más pequeño.
fuente
n>352
(al menos en este fragmento, no sé si depende de mi navegador / máquina) mientras se supone que debe admitir al menos hastan=1000
.n=1000
si usas, por ejemplonode --stack_size=8000
.05AB1E ,
98 bytes-1 Byte gracias al truco de factor principal de Leaky Nun en su respuesta de Pyth
Pruébalo en línea!
Explicación
Solución alternativa de 8 bytes (que no funciona en TIO)
y una solución alternativa de 9 bytes (que funciona en TIO)
fuente
Retina ,
3124 bytes7 bytes gracias a Martin Ender.
Pruébalo en línea!
Cómo funciona
La expresión regular
/^(1+)\1+$/
captura el divisor propio más grande de un cierto número representado en unario. En el código,\1+
se convierte en una sintaxis anticipada.fuente
Mathematica, 30 bytes
fuente
Pyth ,
1398 bytes1 byte gracias a jacoblaw.
Banco de pruebas .
Cómo funciona
El divisor propio más grande es el producto de los factores primos, excepto el más pequeño.
fuente
Python 2 (PyPy) ,
737170 bytesNo es la respuesta más corta de Python, pero esto simplemente pasa por los casos de prueba. TIO maneja entradas de hasta 30,000,000 sin sudar; mi computadora de escritorio maneja 300,000,000 en un minuto.
A un costo de 2 bytes , la condición
n>d
podría usarse para una aceleración de ~ 10%.¡Gracias a @xnor por la
r=[0]*n
idea, que ahorró 3 bytes!Pruébalo en línea!
fuente
l=[0]*n
debería permitirte deshacerte de él-2
.exec
mata un poco la velocidad, pero incluso unwhile
bucle sería más corto que mi enfoque.Haskell,
484643 bytesPruébalo en línea!
Editar: @rogaos guardó dos bytes. ¡Gracias!
Editar II: ... y @xnor otros 3 bytes.
fuente
f 2=1 f n=last[d|d<-[1..n-1],mod n d<1]+f(n-1)
sum
, así que pensé que no es más corta.until
ahorra un poco más:until((<1).mod n)pred(n-1)+f(n-1)
Japt ,
8 + 2 = 1086 bytesPruébalo
Explicación
fuente
-x
cuenta que cuenta como dos bytes de acuerdo con esta publicación . Sin embargo, creo que puede guardar un byte conò2_â1 o
(â
excluye el número original cuando se le da un argumento)â
el argumento me consiguió el ahorro que estaba buscando.õ Å
antes y nos pareció un par de 8 y 9 byters:õ Åx_/k g
,õ Åx_k Å×
,õ Åx_â¬o
. Y al combinarõ
yÅ
con tuxo
truco de genio encontré una solución de 7 bytes :-)MATL, 12 bytes
Pruébalo en MATL Online
Explicación
fuente
PHP , 56 bytes
Pruébalo en línea!
fuente
Prólogo (SWI) , 72 bytes
Pruébalo en línea!
fuente
Cubix , 27
39bytesPruébalo en línea!
Cubified
Míralo correr
0IU
Configure la pila con un acumulador y el número entero inicial. U-turn en el bucle exterior:(?
duplicar la parte superior actual de la pila, disminuir y probar\pO@
Si el bucle cero alrededor del cubo a un espejo, agarra la parte inferior de la pila, salida y detener%\!
si es positivo, mod, relect y prueba.u;.W
si es verdad, gire en u, elimine el resultado del mod y el carril cambie nuevamente al bucle internoU;p+qu;;\(
si falsey, giro en U, elimine el resultado del mod, lleve el acumulador a la parte superior, agregue el divisor entero actual (superior) empuje hacia abajo y gire en U. Limpie la pila para tener solo el acumulador y el número entero actual, disminuya el número entero e ingrese nuevamente al bucle externo.fuente
C # (.NET Core) ,
7472 bytesPruébalo en línea!
fuente
break
aj=0
.En realidad , 12 bytes
Pruébalo en línea!
fuente
Python 3 ,
78 75 7371 bytesNi siquiera cerca de la respuesta de Python de la monja permeable en el recuento de bytes.
Pruébalo en línea!
fuente
Pitón 3 ,
696359 bytes4 bytes gracias a Dennis.
Pruébalo en línea!
Establecí el límite de recursión en 2000 para que esto funcione para 1000.
fuente
Carbón , 37 bytes
Pruébalo en línea!
El enlace es a la versión detallada. Me llevó casi todo el día descubrir cómo podría resolver una pregunta no relacionada con el arte ASCII en Charcoal, pero finalmente lo obtuve y estoy muy orgulloso de mí. :-RE
Sí, estoy seguro de que se puede jugar mucho al golf. Acabo de traducir mi respuesta de C # y estoy seguro de que las cosas se pueden hacer de manera diferente en Charcoal. Al menos resuelve el
1000
caso en un par de segundos ...fuente
Pari / GP ,
3630 bytesPruébalo en línea!
fuente
Python 2 (PyPy) , 145 bytes
Debido a que convertir las competiciones de código de golf en competencias de código más rápido es divertido, aquí hay un algoritmo O ( n ) que, en TIO, resuelve n = 5,000,000,000 en 30 segundos. ( El tamiz de Dennis es O ( n log n )).
Pruébalo en línea!
Cómo funciona
Contamos el tamaño del conjunto.
S = {( a , b ) | 2 ≤ a ≤ n , 2 ≤ b ≤ divisor propio más grande ( a )},
reescribiéndolo como la unión, sobre todos los números primos p ≤ √n, de
S p = {( p ⋅ d , b ) | 2 ≤ d ≤ n / p , 2 ≤ b ≤ d },
y utilizando el principio de inclusión-exclusión :
El | S | = ∑ (−1) m - 1 | S p 1 ∩ ⋯ ∩ S p m | sobre m ≥ 1 y primos p 1 <⋯ < p m ≤ √n,
dónde
S p 1 ∩ ⋯ ∩ S p m = {( p 1 ⋯ p m ⋅ e , b ) | 1 ≤ e ≤ n / ( p 1 ⋯ p m ), 2 ≤ b ≤ p 1 ⋯ p m - 1 e },
| S p 1 ∩ ⋯ ∩ S p m | = ⌊ n / ( p 1 ⋯ p m ) ⌋⋅ ( p 1 ⋯p m- 1 ) ⌋ + 1) - 2) / 2. ⋅ (⌊ n / ( p 1 ⋯ p m
La suma tiene C ⋅ n términos distintos de cero, donde C converge a alguna constante que probablemente sea 6⋅ (1 - ln 2) / π 2 ≈ 0.186544. El resultado final es entonces | S | + n - 1.
fuente
NewStack , 5 bytes
Afortunadamente, en realidad hay un incorporado.
El desglose:
En inglés real:
Ejecutemos un ejemplo para una entrada de 8.
Nᵢ
: Haga una lista de números naturales del 1 al 8:1, 2, 3, 4, 5, 6, 7, 8
;
: Calcule los mayores factores:1, 1, 1, 2, 1, 3, 1, 4
q
. Eliminar el primer elemento:1, 1, 2, 1, 3, 1, 4
Σ
Y toma la suma:1+1+2+1+3+1+4
=13
fuente
1+1+2+1+3+1+4
=13
no8
. Aparte de eso: gran respuesta, entonces +1.Java 8,
787472 bytesPuerto de la respuesta C # de @CarlosAlejo .
Pruébalo aquí
Respuesta anterior (78 bytes):
Pruébalo aquí
Explicación (de la respuesta anterior):
fuente
Lua , 74 bytes
Pruébalo en línea!
fuente
J , 18 bytes
Pruébalo en línea!
fuente
Apilado , 31 bytes
Pruébalo en línea! (Todos los casos de prueba excepto 1000, que excede el límite de tiempo en línea de 60 segundos).
Explicación
fuente
C (gcc) , 53 bytes
Pruébalo en línea!
Cómodamente y rápidamente pasa todos los casos de prueba.
fuente