Encuentra el número más suave

59

Su desafío es encontrar el número más suave en un rango determinado. En otras palabras, encuentre el número cuyo mayor factor primo es el más pequeño.

Un número liso es aquel cuyo mayor factor primo es pequeño. Los números de este tipo son útiles para el algoritmo de transformación rápida de Fourier, el criptoanálisis y otras aplicaciones.

Por ejemplo, en el rango 5, 6, 7, 8, 9, 10, 8 es el número más liso, porque el factor primo más grande de 8 es 2, mientras que todos los demás números tienen un factor primo de 3 o mayor.

Entrada: La entrada será dos enteros positivos, que definen un rango. El número entero mínimo permitido en el rango es 2. Puede elegir si el rango es inclusivo, exclusivo, semi-exclusivo, etc., siempre que se pueda especificar un rango arbitrario dentro de los límites de su idioma. Puede tomar los números a través de la entrada de función, stdin, argumento de línea de comando o cualquier método equivalente para su idioma. No codifica información adicional en la entrada.

Salida: Devuelve, imprime o equivalente uno o más enteros en el rango de entrada que son máximamente suaves (mínimo factor máximo). Devolver múltiples resultados es opcional, pero si elige hacerlo, los resultados deben estar claramente delimitados. El formato de salida nativo está bien para múltiples resultados.

Indique en su respuesta cómo está tomando entrada y dando salida.

Puntuación: Código de golf. Cuenta por caracteres si está escrito en ASCII, o 8 * bytes / 7 si no está en ASCII.

Casos de prueba:

Nota: Estos son rangos de estilo Python, incluidos los de gama baja pero no los de gama alta. Cambie según corresponda a su programa. Solo un resultado es necesario.

smooth_range(5,11)
8
smooth_range(9,16)
9, 12
smooth_range(9,17)
16
smooth_range(157, 249)
162, 192, 216, 243
smooth_range(2001, 2014)
2002
isaacg
fuente
¿Son aceptables los rangos especificados como (inicio, longitud) en lugar de (inicio, final)?
CodesInChaos
1
@CodesInChaos Claro. Está cubierto por la cláusula "o lo que sea".
isaacg
3
No veo el punto de penalizar las respuestas que no son ASCII. Sería más simple contar bytes en todos los casos.
nyuszika7h
1
@ nyuszika7h Ascii es significativamente más pequeño que un byte, solo usa 7 bits. Por lo tanto, denoto un carácter por 7 bits, y escalo otros idiomas en consecuencia. Sin embargo, si el idioma no es ASCII pero puede incluir todos sus caracteres en 7 bits, no aplicaré el recargo. Ver J / K vs. APL. tl; dr Bytes es más simple, pero da APL et. Alabama. Una ventaja sutil pero injusta.
isaacg
3
@isaacg estás fomentando la creación de pseudo-idiomas usando juegos de caracteres más pequeños. si calificamos los juegos de caracteres de 7 bits diferentes de los juegos de caracteres de 8 bits, alguien puede empaquetar la mayoría de los idiomas modernos en 6 bits (64 caracteres nos dan AZ, 0-9, un puñado de espacios en blanco, 20 signos de puntuación y algunos de sobra) .
Sparr

Respuestas:

99

CJam - 13

q~,>{mfW=}$0=

Pruébalo en http://cjam.aditsu.net/

Ejemplo de entrada: 2001 2014
Ejemplo de salida:2002

Explicación:

q~lee y evalúa la entrada, empujando los 2 números en la pila (digamos min y max)
,hace que una matriz [0 1 ... max-1]
>corte la matriz comenzando en min, resultando en [min ... max-1]
{…}$ordena la matriz usando el bloque para calcular la clave de clasificación
mfobtiene una matriz con todos los factores primos de un número, en orden
W=obtiene el último elemento de la matriz (W = -1), obteniendo así el factor primo más grande para ser utilizado como La clave de clasificación
0=obtiene el primer elemento de la matriz (ordenada)

aditsu
fuente
38
Bueno, supongo que eso es todo.
Eric Tressler
55
Necesito agregar una función factorizar a pyth.
isaacg
66
Este lenguaje es la magia.
Brobin
8
Esto es lo más cercano a tirar de algunos HQ9 + s ** t como puede ser sin convertirse en una escapatoria. ¡Increíble!
Ingo Bürk
25
ノ ༼ ຈ ل͜ ຈ ༽ ノmfWalguien lo resolvió en 13 caracteres.
interconexiones están hechas de catz
66

Regex ( sabor .NET PCRE), 183 129 bytes

¡No intentes esto en casa!

Esto no es realmente un contendiente para la victoria. Pero Eric Tressler sugirió resolver este problema con nada más que una expresión regular, y no pude resistir intentarlo. Esto podría ser posible también en PCRE (e incluso más corto, ver más abajo), pero elegí .NET porque mi solución necesita mirar hacia atrás de longitud arbitraria. Aquí vamos:

(?<=^(1+),.*)(?=\1)(?=((11+)(?=.*(?=\3$)(?!(11+?)\4+$))(?=\3+$)|(?!(11+)\5+$)1+))(?!.+(?=\1)(?:(?!\2)|(?=((11+)(?=.*(?=\7$)(?!(11+?)\8+$))(?=\7+$)|(?!(11+)\9+$)1+)).*(?=\2$)(?=\6)))1+

La entrada se codifica como un rango inclusivo separado por comas, donde ambos números se dan en notación unaria usando 1s. La coincidencia será el S1 al final, donde Ses el número más suave en el rango. Los lazos se rompen a favor del número más pequeño.

Entonces, el segundo ejemplo de la pregunta sería la siguiente cadena (coincidencia subrayada)

111111111,1111111111111111
                 =========

Se basa en la expresión regular de verificación principal (por ahora bastante conocida) , cuyas variaciones están incrustadas allí 6 veces.

Aquí hay una versión que usa espacios libres y comentarios para aquellos que quieren saber qué está pasando.

# Note that the beginning of the match we're looking for is somewhere
# in the second part of the input.
(?<=^(1+),.*)          # Pick up the minimum range MIN in group 1
(?=\1)                 # Make sure there are at least MIN 1s ahead

                       # Now there will be N 1s ahead of the cursor
                       # where MIN <= N <= MAX.


(?=(                   # Find the largest prime factor of this number
                       # store it in group 2.
  (11+)                # Capture a potential prime factor P in group 3
  (?=                  # Check that it's prime
    .*(?=\3$)          # Move to a position where there are exactly 
                       # P 1s ahead
    (?!(11+?)\4+$)     # Check that the remaining 1s are not composite
  )
  (?=\3+$)             # Now check that P is a divisor of N.
|                      # This does not work for prime N, so we need a 
                       # separate check
  (?!(11+)\5+$)        # Make sure that N is prime.
  1+                   # Match N
))

(?!                    # Now we need to make sure that here is not 
                       # another (smaller) number M with a smaller 
                       # largest prime factor

  .+                   # Backtrack through all remaining positions
  (?=\1)               # Make sure there are still MIN 1s ahead

  (?:
    (?!\2)             # If M is itself less than P we fail 
                       # unconditionally.
  |                    # Else we compare the largest prime factors.
    (?=(               # This is the same as above, but it puts the
                       # prime factor Q in group 6.
      (11+)
      (?=
        .*(?=\7$)
        (?!(11+?)\8+$)
      )
      (?=\7+$)
    |
      (?!(11+)\9+$)
      1+
    ))
    .*(?=\2$)          # Move to a position where there are exactly 
                       # P 1s ahead
    (?=\6)             # Try to still match Q (which means that Q is
                       # less than P)
  )
)
1+                     # Grab all digits for the match

Puedes probarlo en línea aquí . Sin embargo, no intente entradas demasiado grandes, no garantizo el rendimiento de este monstruo.

Editar:

Terminé portando esto a PCRE (que solo requiere dos pasos), y acortando la expresión regular en casi un tercio. Aquí está la nueva versión:

^(1+),.*?\K(?=\1)(?=((11+)(?=.*(?=\3$)(?!(11+?)\4+$))(?=\3+$)|(?!(11+)\5+$)1+))(?!.+(?=\1)(?:(?!\2)|(?=((?2))).*(?=\2$)(?=\6)))1+

Esto es esencialmente lo mismo, con dos cambios:

  • PCRE no es compatible con mirar atrás de longitud arbitraria (que solía obtener MINen el grupo 1). Sin embargo, PCREadmite \Kqué restablece el comienzo del partido a la posición actual del cursor. Por lo tanto , se (?<=^(1+),.*)convierte en lo ^(1+),.*?\Kque ya guarda dos bytes.
  • Los ahorros reales provienen de la función de recurrencia de PCRE. En realidad, no estoy usando la recursividad, pero puede usarla (?n)para hacer coincidir el grupo nnuevamente, similar a una llamada de subrutina. Dado que la expresión regular original contenía el código para encontrar el factor primo más grande de un número dos veces, pude reemplazar todo el volumen del segundo con un simple (?2).
Martin Ender
fuente
37
Santa Madre de Dios
Newb
1
@Timwi Necesito verificar que el factor primo más grande (grupo 3o 7) sea realmente primo. Esto requiere que haya otra copia del factor después de capturarlo por primera vez, lo que no sería el caso de los números primos. Si bien evito eso en .NET poniendo un vistazo atrás en algún lugar allí para poder retroceder un poco para la verificación, esto no sería posible en la versión PCRE más corta debido a la falta de retrospectivas de longitud variable. Probablemente sea posible acortar ese bit, pero no creo que solo cambie +a *funcionar.
Martin Ender
2
@MartinEnder ¡Hola! Me imagino que hace mucho tiempo que superaste este desafío, pero acabo de navegar, vi una solución de expresiones regulares y no pude evitar ignorar por completo tu advertencia en la parte superior de esta publicación :) Me resulta difícil jugar el código de otras personas, así que después de mirar su expresión regular y confundirme, lo intenté desde cero y se me ocurrió esto: (.*),.*?\K(?=(..+)((?=((?(R)\6|\2))*$).*(?=\4$)(?!(..+)\5+$)))(?!.+(?=\1)(?=(..+)(?3)).*(?!\2)\6).+ 99 bytes en PCRE. Además, he encontrado mucho de su trabajo en este sitio y soy un gran admirador: D ¡Espero una batalla de expresiones regulares en el futuro!
jaytea
1
Estaba jugando al golf de código con ese comentario, así que solo pondré el apéndice aquí: puede eliminar 4b quitando \4$el lookahead y pegándolo después del lookahead negativo, pero esto afecta gravemente el rendimiento (cada subgrupo de dígitos <= \ 4 se comprueba la composición en lugar de solo \ 4 en sí mismo) y falla en entradas más largas.
jaytea
1
@jaytea Perdón por tardar una eternidad en responderte sobre esto. Como escribiste el artículo desde cero, creo que deberías publicar una respuesta por separado. Esa es una gran puntuación y te mereces el crédito por ello. :)
Martin Ender
16

Regex (sabor PCRE), 66 (65🐌) bytes

Inspirado al ver que tanto Martin Ender como Jaytea , dos genios de expresiones regulares, escribieron soluciones de expresiones regulares para este código de golf, escribí la mía desde cero. La famosa expresión regular de verificación principal no aparece en ninguna parte de mi solución.

No leas esto si no quieres que te estropeen un poco de magia regex unaria. Si desea intentar descubrir esta magia usted mismo, le recomiendo comenzar resolviendo algunos problemas en ECMAScript regex:

  1. Haga coincidir los números primos (si aún no está familiarizado con hacer esto en expresiones regulares)
  2. Combina poderes de 2 (si aún no lo has hecho). O simplemente trabaje en Regex Golf , que incluye Prime y Powers. Asegúrese de hacer los conjuntos de problemas Clásico y Teukon.
  3. Encuentre la forma más corta de hacer coincidir las potencias de N donde N es algo constante (es decir, especificado en la expresión regular, no en la entrada) que puede ser compuesto (pero no es obligatorio que lo sea). Por ejemplo, empareja potencias de 6.

  4. Encuentre una forma de hacer coincidir las enésimas potencias, donde N es una constante> = 2. Por ejemplo, combina cuadrados perfectos. (Para un calentamiento, combina poderes primarios ).

  5. Une las declaraciones de multiplicación correctas. Empareja números triangulares.

  6. Haga coincidir los números de Fibonacci (si está tan loco como yo), o si desea apegarse a algo más corto, haga coincidir las declaraciones correctas de exponenciación (para un calentamiento, regrese como un logaritmo en la base 2 de una potencia de 2) bono, haga lo mismo para cualquier número, redondeándolo como desee), o números factoriales (para un calentamiento, iguale los números primarios ).

  7. Une números abundantes (si estás tan loco como yo)

  8. Calcule un número irracional con la precisión solicitada (por ejemplo, divida la entrada por la raíz cuadrada de 2, devolviendo el resultado redondeado como una coincidencia)

(El motor de expresiones regulares que escribí puede ser de ayuda, ya que es muy rápido en expresiones regulares matemáticas simples e incluye un modo numérico unario que puede probar rangos de números naturales (pero también tiene un modo de cadenas que puede evaluar expresiones regulares no unitarias o unarias). con delimitadores). De manera predeterminada, es compatible con ECMAScript, pero tiene extensiones opcionales (que pueden agregar selectivamente subconjuntos de PCRE, o incluso anticipación molecular, algo que ningún otro motor de expresiones regulares tiene).

De lo contrario, siga leyendo y también lea este GitHub Gist (advertencia, muchos spoilers) que narra el viaje de empujar la expresión regular ECMAScript para abordar las funciones de números naturales de dificultad creciente (comenzando con el conjunto de acertijos de teukon, no todos matemáticos, lo que provocó esto viaje).

Al igual que con las otras soluciones de expresiones regulares para este problema, la entrada se da como dos números en bijetivo unario, separados por una coma, que representan un rango inclusivo. Solo se devuelve un número. La expresión regular podría modificarse para devolver todos los números que comparten el mismo factor primo más grande más pequeño, como coincidencias separadas, pero eso requeriría mirar hacia atrás de longitud variable y poner \Kuna anticipación o devolver el resultado como una captura en lugar de una coincidencia.

La técnica utilizada aquí de división implícita repetida por el factor primo más pequeño es idéntica a la utilizada en las cadenas Match cuya longitud es una cuarta respuesta de potencia que publiqué hace un tiempo.

Sin más preámbulos: ((.+).*),(?!.*(?=\1)(((?=(..+)(\5+$))\6)*)(?!\2)).*(?=\1)\K(?3)\2$

Puedes probarlo aquí.

Y la versión de espacio libre, con comentarios:

                        # No ^ anchor needed, because this algorithm always returns a
                        # match for valid input (in which the first number is less than
                        # or equal to the second number), and even in /g mode only one
                        # match can be returned. You can add an anchor to make it reject
                        # invalid ranges.

((.+).*),               # \1 = low end of range; \2 = conjectured number that is the
                        # smallest number in the set of the largest prime factor of each
                        # number in the range; note, it is only in subsequent tests that
                        # this is implicitly confined to being prime.
                        # We shall do the rest of our work inside the "high end of range"
                        # number.

(?!                     # Assert that there is no number in the range whose largest prime
                        # factor is smaller than \2.
  .*(?=\1)              # Cycle tail through all numbers in the range, starting with \1.

  (                     # Subroutine (?3):
                        # Find the largest prime factor of tail, and leave it in tail.
                        # It will both be evaluated here as-is, and later as an atomic
                        # subroutine call. As used here, it is not wrapped in an atomic
                        # group. Thus after the return from group 3, backtracking back
                        # into it can increase the value of tail – but this won't mess
                        # with the final result, because only making tail smaller could
                        # change a non-match into a match.

    (                   # Repeatedly divide tail by its smallest prime factor, leaving
                        # only the largest prime factor at the end.

      (?=(..+)(\5+$))   # \6 = tool to make tail = \5 = largest nontrivial factor of
                        # current tail, which is implicitly the result of dividing it
                        # by its smallest prime factor.
      \6                # tail = \5
    )*
  )
  (?!\2)                # matches iff tail < \ 2
)

# now, pick a number in the range whose largest prime factor is \2
.*(?=\1)                # Cycle tail through all numbers in the range, starting with \1.
\K                      # Set us up to return tail as the match.
(?3)                    # tail = largest prime factor of tail
\2$                     # Match iff tail == \2, then return the number whose largest
                        # prime factor is \2 as the match.

El algoritmo se puede portar fácilmente a ECMAScript reemplazando la llamada de subrutina con una copia de la subrutina y devolviendo la coincidencia como un grupo de captura en lugar de usar \ K. El resultado es 80 bytes de longitud:

((x+)x*),(?!.*(?=\1)((?=(xx+)(\4+$))\5)*(?!\2)).*(?=\1)(((?=(xx+)(\8+$))\9)*\2$)

Pruébalo en línea!

Tenga en cuenta que ((.+).*)se puede cambiar a ((.+)+), bajando el tamaño en 1 byte (de 66 a 65 bytes ) sin pérdida de la funcionalidad correcta, pero la expresión regular explota exponencialmente en la lentitud.

Pruébalo en línea! (Versión de desaceleración exponencial ECMAScript de 79 bytes)

Código muerto
fuente
11

Pitón 2, 95

i=input()
for a in range(*i):
 s=a;p=2
 while~-a:b=a%p<1;p+=1-b;a/=p**b
 if p<i:i=p;j=s                                        
print j

Encuentra la suavidad de los números por división de prueba hasta que el número sea 1. ialmacena la suavidad más pequeña hasta ahora, jalmacena el número que dio esa suavidad.

Gracias a @xnor por los campos de golf.

isaacg
fuente
1
Eso if/elsetiene que ser acortable. Mi primer pensamiento es b=a%p<1;p+=1-b;a/=p**b. O un ejecutivo que ejecuta uno de los dos en una cadena intercalada. Además, tal vez while~-afuncione.
xnor
isaacg - ¡Me encanta esta respuesta! ¡Qué manera tan brillante encontraste para buscar el factor primo más grande! He actualizado mi respuesta para pedir prestado su método, con crédito en el método.
Todd Lehman
Gran solución! Utilizando s,p=a,2, i,j=p,s, @ ideas de XNOR, la eliminación de la sangría redundante y poner el bloque, mientras que en una sola línea de 95 caracteres produce. No estoy seguro de cómo se te ocurrió 98 ...
Falko
este código está lleno de emoticonos, :)
Rosenthal
@Falko esos dos cambios no guardan caracteres. 7-> 7.
isaacg
10

J, 22 20 19 caracteres

({.@/:{:@q:)@(}.i.)

P.ej

   2001 ({.@/: {:@q:)@(}. i.) 2014
2002

(Las funciones que toman dos argumentos están infijadas en J.)

Luciérnaga
fuente
También tuve una grieta en eso, no lo entendí tan corto como esta respuesta. Aún así:(#~ (= <./)@:(i:"1&1)@:*@:(_&q:))@:([ + i.@-~)
Augıʇǝɥʇuʎs
Aquí {:es lo mismo >./y ahorra 1 byte.
randomra
@randomra Tienes razón, ¡buena decisión!
FireFly
Hermosa. TIO si desea agregarlo: ¡ Pruébelo en línea!
Jonás
9

Haskell, 96 94 93 86 80 caracteres

x%y|x<2=y|mod x y<1=div x y%y|0<1=x%(y+1)
a#b=snd$minimum$map(\x->(x%2,x))[a..b]

uso a través de GHCi (un shell de Haskell):

>5 # 9
8
>9 # 15
9

EDITAR: ahora un algoritmo mucho más simple.

esta solución incluye ambos números en el rango (entonces 8 # 9y 7 # 8son ambos 8)

explicación:

la función (%) toma dos parámetros, x e y. cuando y es 2, la función devuelve la suavidad de x.

el algoritmo de aquí es simple: obtenga la lista combinada de todas las suavidades de los números en la entrada con cada suavidad almacenando una referencia a su número original, ordene para obtener el más pequeño y devuelva su número de referencia.


Aquí hay una versión de JavaScript sin golf con el mismo algoritmo:

function smoothness(n,p)
{
    p = p || 2
    if (x == 1)
        return p
    if (x % p == 0)
        return smoothness(x/p, p)
    else
        return smoothness(x,p+1);
}
function smoothnessRange(a, b)
{
    var minSmoothness = smoothness(a);
    var min=a;
    for(var i=a+1;i <= b;i++)
        if(minSmoothness > smoothness(i))
        {
            minSmoothness = smoothness(i)
            min = i
        }
    return min;
}
orgulloso Haskeller
fuente
¿Sería posible alias mínimo a algo más corto? Parece que salvaría a algunos personajes.
isaacg
Lo intenté, pero debido a la restricción del monomorfismo, en realidad cuesta un personaje
orgulloso Haskeller
¿No puedes simplemente hacer m = mínimo? Haskell sigue siendo un misterio.
isaacg
1
@isaacg Para evitar la restricción del monomorfismo, uno tendría que escribirm l=minimum l
orgulloso Haskeller
2
Iba a publicar una solución de Haskell, hasta que vi la tuya que supera incluso mi versión incompleta ... +1
nyuszika7h
9

Mathematica, 61 45 39 caracteres

Range@##~MinimalBy~Last@*FactorInteger&

Implementación muy sencilla de la especificación como una función sin nombre.

  • Obtenga el rango (incluido).
  • Factoriza todos los enteros.
  • Encuentre el mínimo, ordenado por el factor primo más grande.
Martin Ender
fuente
8

Lua - 166 caracteres

Yo no no tenía (todavía!) Reputación suficiente para comentar sobre la solución de AndoDaan , pero aquí hay algunas mejoras en su código

a,b=io.read("*n","*n")s=b for i=a,b do f={}n=i d=2 while n>1 do while n%d<1 do f[#f+1]=d n=n/d end d=d+1 end p=math.max(unpack(f))if p<s then s=p c=i end end print(c)

Cambios:

  • El n%d==0por el n%d<1cual es equivalente en este caso
  • Eliminado un espacio
  • Reemplazado table.insert(f,d)por f[#f+1]=d ( #fes el número de elementos de f)
Adriweb
fuente
Ah, me alegro de haber echado un vistazo aquí. Ah, los dos primeros deberían haberlo comprobado y atrapado, pero su tercera mejora es nueva para mí (quiero decir, simplemente diferente de lo que estoy acostumbrado). Eso me va a ayudar mucho aquí y en golf.shinh.com. ¡Gracias!
AndoDaan
8

Bash + coreutils, 56 bytes

seq $@|factor|sed 's/:.* / /'|sort -nk2|sed '1s/ .*//;q'

La entrada proviene de exactamente dos argumentos de línea de comandos (¡Gracias @ nyuszika7h !!!). La salida es un resultado singular impreso en STDOUT.

  • seq proporciona el rango de números, uno por línea, a partir de los argumentos de la línea de comandos.
  • factorlee esos números y genera cada número seguido de dos puntos y la lista ordenada de factores primos de ese número. Entonces el factor primo más grande está al final de cada línea.
  • El primero sedelimina los dos puntos y todo, excepto el último / mayor factor primo, por lo que deja una lista de cada número (columna 1) y su factor primo más grande (columna 2).
  • sort numéricamente en orden creciente por la columna 2.
  • La sedlínea final coincide con la línea 1 (número cuyo factor primo más grande es el más pequeño de la lista), elimina todo, incluido y después del primer espacio, luego se cierra. sedimprime automáticamente el resultado de esta sustitución antes de salir.

Salida:

$ ./smooth.sh 9 15
12
$ ./smooth.sh 9 16
16
$ ./smooth.sh 157 249
162
$ ./smooth.sh 2001 2014
2002
$ 

Los rangos de notas en este contexto incluyen ambos puntos finales.

Trauma digital
fuente
1
seq $@es 3 bytes más corto, si puede suponer que solo hay dos argumentos.
nyuszika7h
@ nyuszika7h Buena idea, ¡gracias!
Trauma digital
5

Pitón 2, 67

f=lambda R,F=1,i=2:[n for n in range(*R)if F**n%n<1]or f(R,F*i,i+1)

Pensar en otro golf me dio la idea de un nuevo algoritmo para verificar la suavidad, de ahí la respuesta tardía.

La factorización prima del factorial i!incluye exactamente los primos como máximo i. Entonces, si nes un producto de primos distintos, su suavidad (factor primo más grande) es el más pequeño ipara el cual nes un divisor i!. Para tener en cuenta los factores primos repetidos en n, podemos utilizar una potencia suficientemente alta de i!. En particular, es (i!)**nsuficiente.

El código intenta aumentar los factoriales F=i!, actualizados de forma recursiva. Filtramos los divisores de Fen el rango de entrada, y los enviamos si hay alguno, y de lo contrario pasamos a (i+1)!.

Caso de prueba:

>> f([157, 249])
[162, 192, 216, 243]
xnor
fuente
4

C,  149   95

Respuesta editada:

No puedo reclamar crédito por esta solución. Esta respuesta actualizada toma prestado el hermoso método utilizado por Isaac en su solución Python. Quería ver si era posible escribirlo en C como un anidado for/ whilebucle sin llaves, ¡y lo es!

R(a,b,n,q,p,m){for(;a<b;m=p<q?a:m,q=p<q?p:q,n=++a,p=2)while(n>1)if(n%p)p++;else n/=p;return m;}

Explicación:

  • Función R(a,b,n,q,p,m)explora el rango ade b-1y devuelve el primer número más suave encontrado. Invocación requiere la adhesión a la siguiente forma: R(a,b,a,b,2,0)por lo que las variables dentro de la función se inicializan de manera efectiva como sigue: n=a;q=b;p=2;m=0;.

Respuesta original :

Esta fue mi respuesta original ...

P(n,f,p){for(;++f<n;)p=p&&n%f;return p;}
G(n,f){for(;--f>1;)if(n%f==0&&P(f,1,1))return f;}
R(a,b,p,n){for(;++p;)for(n=a;n<b;n++)if(G(n,n)==p)return n;}

Explicación:

  • La función P(n,f,p)prueba el valor nde primalidad y devuelve verdadero (distinto de cero) si nes primo o falso (cero) si nno es primo. fy pambos deben pasarse como 1.
  • La función G(n,f)devuelve el máximo factor primo de n. fdebe pasarse como n.
  • Función R(a,b,p,n)explora el rango ade b-1y devuelve el primer número más suave encontrado. pdebe pasarse como 1. npuede ser cualquier valor.

Conductor de prueba:

test(a,b){printf("smooth_range(%d, %d)\n%d\n",a,b,S(a,b,1,0));}
main(){test(5,11);test(9,16);test(9,17);test(157,249);test(2001,2014);}

Salida:

smooth_range(5, 11)
8
smooth_range(9, 16)
9
smooth_range(9, 17)
16
smooth_range(157, 249)
162
smooth_range(2001, 2014)
2002
Todd Lehman
fuente
Yo diría que esto no cumple con la cláusula "No codificar información adicional en la entrada".
Alchymist
@Alchymist: puede que tengas razón ... pero no creo que haya ninguna información adicional real en los seudoargumentos. Al menos no hay ninguna información que sea algún tipo de pista sobre la respuesta.
Todd Lehman
4

Haskell - 120

import Data.List
import Data.Ord
x!y=(minimumBy(comparing(%2)))[x..y]
x%y|x<y=y|x`mod`y==0=(x`div`y)%y|otherwise=x%(y+1)

Ejemplo de uso:

> 5 ! 10
8
> 9 ! 15
9
> 9 ! 16
16
> 157 ! 248
162
> 2001 ! 2013
2002
Taylor Fausak
fuente
1
¿No podrías usar en <1lugar de ==0?
dfeuer
Sí, eso sería una buena mejora. Hay muchas pequeñas cosas que podrían hacerse mejor. Afortunadamente, esta respuesta ya lo hace todas: codegolf.stackexchange.com/a/36461
Taylor Fausak
4

Q, 91 caracteres K, 78 caracteres

{(x+{where x=min x}{(-2#{x div 2+(where 0=x mod 2_til x)@0}\[{x>0};x])@0}'[(x)_til y+1])@0}

k probablemente afeitaría una docena de caracteres

editar: de hecho, tratar el límite superior como no inclusivo esta vez

{*:x+{&:x=min x}{*:-2#{6h$x%2+*:&:x={y*6h$x%y}[x]'[2_!x]}\[{x>0};x]}'[(x)_!y]}
Arthur B
fuente
4

Nota: esta respuesta no está permitida.

Esta respuesta utiliza múltiples características de Pyth agregadas después de que se le preguntó el desafío.

Agregué otra nueva característica, llamando al rango unario en una tupla de 2 elementos, que acorta la solución en dos caracteres, a esto:

Pyth , 7

hoePNUQ

La entrada ahora se toma separada por comas. El resto es igual.


Esta respuesta utiliza una característica de Pyth que se agregó después de que se hizo esta pregunta, específicamente después de ver la maravillosa solución CJam de @ aditsu. Dicho esto, quería demostrar lo que ha hecho posible agregar esa característica. La característica es P, que es una función arity-1 que en la entrada entera devuelve una lista de todos los factores primos de la entrada, ordenados de menor a mayor.

Pyth , 9

hoePNrQvw

Utiliza rangos de estilo Python, nueva línea separada en STDIN. Produce la solución más pequeña para STDOUT.

Explicación:

      Q = eval(input())                         Implicit, because Q is present.
h     head(                                     First element of
 o         order_by(                            Sort, using lambda expression as key.
                    lambda N:                   Implicit in o
  e                          end(               Last element of
   PN                            pfact(N)),     List containing all prime factors of N.
  r                 range(                      Python-style range, lower inc, upper exc.
   Q                      Q,                    A variable, initialized as shown above.
   vw                     eval(input()))))      The second entry of the range, same way.

Pruebas:

$ newline='
'

$ echo "9${newline}16" | ./pyth.py -c 'hoePNrQvw'
9

$ echo "9${newline}17" | ./pyth.py -c 'hoePNrQvw'
16

$ echo "157${newline}249" | ./pyth.py -c 'hoePNrQvw'
162

$ echo "2001${newline}2014" | ./pyth.py -c 'hoePNrQvw'
2002
isaacg
fuente
@ MartinBüttner Sí, como lo sugiere su comentario sobre la solución
CJam
@ MartinBüttner Sí, P, es la nueva característica. Pondré eso en la respuesta.
isaacg
1
Permitido o no, no solo me gusta, sino que también creo que esas "macros" cortas son legibles si prestas atención, después de todo, se convierten en Python. Algo tiene que decirse para un lenguaje de golf que sea bueno para el golf pero que no necesariamente ofusque.
Kuba Ober
@KubaOber Gracias, Kuba. Esa siempre ha sido mi intención al escribir Pyth, para que sea lo más golfizado y legible posible. Me alegra que esté funcionando.
isaacg
3

Lua - 176 caracteres

a,b=io.read("*n","*n")s=b for i=a,b do f={}n=i d=2 while n>1 do while n%d==0 do table.insert(f, d)n=n/d end d=d+1 end p=math.max(unpack(f))if p<s then s=p c=i end end print(c)

Realmente debería dejar de jugar al golf en Lua. No tiene sentido.

AndoDaan
fuente
14
En mi humilde opinión, el golf de código es como el boxeo: hay clases de peso. Es posible que un idioma determinado no gane directamente, pero es divertido e ilumina el golf dentro de esa clase / idioma.
Michael Easter
3

Clojure - 173 170 caracteres

Soy un novato de Clojure. Golfizado:

(defn g[x,d](if(and(= 0(mod x d))(.isProbablePrime(biginteger d) 1))d 0))(defn f[i](apply max-key(partial g i)(range 2(inc i))))(defn s[a,b](first(sort-by f(range a b))))

Ejecuciones de muestra:

Los rangos incluyen los de gama baja, excluyen los de gama alta: [a, b) Solo imprime uno de los números más suaves, si se producen múltiples.

(println (s 5 11))
(println (s 9 16))
(println (s 9 17))
(println (s 157, 249))
(println (s 2001, 2014))

rendimientos:

bash$ java -jar clojure-1.6.0.jar range.clj
8
9
16
192
2002

Sin golf:

(defn g [x,d] (if (and (= 0(mod x d)) (.isProbablePrime (biginteger d) 1)) d 0))
(defn f [i] (apply max-key (partial g i) (range 2 (inc i))))
(defn s [a,b] (first (sort-by f (range a b))))
Michael Easter
fuente
1
Un rango que incluye el extremo inferior y excluye el extremo superior generalmente se escribe [a, b).
murgatroid99
sí, gracias por la nota
Michael Easter
3

Rubí, 65 62

require'prime'
s=->a,b{(a..b).min_by{|x|x.prime_division[-1]}}

Con disculpas a https://codegolf.stackexchange.com/a/36484/6828 , esta es la versión golfizada (y ligeramente simplificada) de eso. Utiliza un rango inclusivo ya que es un personaje más corto.

1.9.3-p327 :004 > s[157,249]
 => 192 
1.9.3-p327 :005 > s[5,11]
 => 8 
1.9.3-p327 :006 > s[9,15]
 => 12 
1.9.3-p327 :007 > s[9,16]
 => 16 

Y gracias a YenTheFirst por salvar tres personajes.

histocrat
fuente
1
De hecho, puede escapar sin el [0], ya que la comparación de matrices priorizará el primer elemento de todos modos. Esto dará resultados diferentes, pero aún correctos.
YenTheFirst
3

C # LINQ: 317 303 289 262

using System.Linq;class P{static void Main(string[]a){System.Console.Write(Enumerable.Range(int.Parse(a[0]),int.Parse(a[1])).Select(i=>new{i,F=F(i)}).Aggregate((i,j)=>i.F<j.F?i:j).i);}static int F(int a){int b=1;for(;a>1;)if(a%++b<1)while(a%b<1)a/=b;return b;}}

Sin golf:

using System.Linq;

class P
{
  static void Main(string[]a)
  {
    System.Console.Write(
      Enumerable.Range(int.Parse(a[0]), int.Parse(a[1])) //create an enumerable of numbers containing our range (start, length)
        .Select(i => new { i, F = F(i) }) //make a sort of key value pair, with the key (i) being the number in question and the value (F) being the lowest prime factor
        .Aggregate((i, j) => i.F < j.F ? i : j).i); //somehow sort the array, I'm still not entirely sure how this works
  }
  static int F(int a)
  {
    int b=1;
    for(;a>1;)
      if(a%++b<1)
        while(a%b<1)
          a/=b;
    return b;
  }
}

Toma el inicio y la longitud de la línea de comando y devolverá el número liso más grande.

Usé respuestas de aquí y de aquí para hacer mi respuesta.

¡Gracias a VisualMelon por ajustarlo y eliminar 12 bytes! También me deshice de las llaves en el caso de que ahorre 2 bytes, y CodeInChaos señaló algunas cosas obvias que me perdí (gracias de nuevo).

ldam
fuente
Un par de cosas pequeñas de propósito general, puede guardar 4 bytes Fdefiniendo int bjunto a m. En un par de lugares de llevar a cabo la comparación a%b==0, y ay bes siempre positiva se puede cortar un byte para cada comprobando si es inferior a 1 a%b<1. También puede guardar un byte incrementando bla condición if en a%++b<0lugar de for for inicializándolo en 1. También creo que en este caso es más barato simplemente calificar completamente System.Console.WriteLiney evitar la namespacecláusula.
VisualMelon
@VisualMelon Gracias, actualizado con tus ideas :)
ldam
La m=...:m;cosita queda fuera del bucle while. Por lo tanto, puede soltar m=0,y reemplazar return m;con return m=b>m?b:m;. Entonces, puedes soltarlo por m=...:m;completo.
tomsmeding
Puede sonar extraño, pero esto es, para mí, menos legible que CJam y J. ¿Supongo que C # fue diseñado para ser detallado, y los intentos de hacerlo menos lo hacen ilegible? Hmm ....
Kuba Ober
No, estoy de acuerdo, LINQ parece un demonio cuando lo ves aquí y allá y nunca juegas con él. Sin embargo, una vez que lo entiendes, es realmente genial :) Dicho esto, todavía no entiendo completamente cómo Aggregatefunciona, simplemente lo intenté después de verlo en otra respuesta para llegar a mi nuevo objeto en lugar de solo un campo dentro de él, y simplemente pasó a funcionar perfectamente :)
ldam
2

R, 83

library(gmp)
n=a:b
n[which.min(lapply(lapply(lapply(n,factorize),max),as.numeric))]

donde se asigna la parte inferior del rango de entrada y se asigna ala parte superior (inclusive) b.

gmpes un paquete que está disponible en CRAN. Se sintió sucio hasta que vi esa absurda mffunción en CJam. Instalar escribiendo install.packages("gmp")en la consola.

Shadowtalker
fuente
1
Si está usando lapply3 veces, es posible que desee alias (es decir, l=lapplyy luego usar l(...). De manera similar, dado que factorizees la única función que usa desde el paquete gmp, puede usarla en gmp::factorizelugar de cargar la biblioteca y luego usarla factorize. Su código se convertiría en l=lapply;n=a:b;n[which.min(l(l(l(n,gmp::factorize),max),as.numeric))]69 bytes.
plannapus
2

PowerShell - 85

($args[0]..$args[1]|sort{$d=2
while($_-gt1){while(!($_%$d)){$m=$d;$_/=$d}$d++}$m})[0]

Esto ordenará un rango de números (inclusive) basado en el factor primo máximo de cada número. Devuelve el elemento ordenado más bajo.

> smooth 5 10
8
> smooth 9 15
12
> smooth 9 16
16
> smooth 157 248
243
> smooth 2001 2013
2002
Rynant
fuente
2

J - 16 char

Usando el estilo de rango ( inicio , longitud ), según lo permitido por los comentarios.

(0{+/:{:@q:@+)i.

Para ser usado como un verbo diádico: el argumento izquierdo es el comienzo , el derecho es la longitud .

   5 (+)i. 6              NB. range
5 6 7 8 9 10
   5 (q:@+)i. 6           NB. prime factorizations
5 0 0
2 3 0
7 0 0
2 2 2
3 3 0
2 5 0
   5 ({:@q:@+)i. 6        NB. largest prime factors
5 3 7 2 3 5
   5 (+/:{:@q:@+)i. 6     NB. sort range by smallest factors
8 6 9 5 10 7
   5 (0{+/:{:@q:@+)i. 6   NB. take first entry
8
   f=:(0{+/:{:@q:@+)i.    NB. can also be named
   2001 f 13
2002

Una solución ( inicio , fin ) es +2 caracteres y excluye el final; incluyendo el final es +2 más. Pero en el lado positivo, se ve bastante bien ya que combinamos todas las {llaves}.

(0{}./:{:@q:@}.)i.    NB. excluding
(0{}./:{:@q:@}.)1+i.  NB. including
Algoritmo de tiburón
fuente
2

En serio, 8 * 14/7 = 16 (no competitivo)

,x;`yM`M;m@í@E

En serio se creó después de este desafío, pero quería publicar esta respuesta porque ejemplifica el tipo de desafíos en los que Seriously es bueno.

Pruébalo en línea!

Explicación:

,x;`yM`M;m@í@E
,x;             make two copies of range(a,b) (a,b = input())
   `  `M;       make two copies of the result of the map:
    yM            push maximum prime factor
         m@í    push index of minimum element from prime factors
            @E  push element from range with given index
Mego
fuente
2

Pyth , 7 bytes

.mePbrF

Pruébalo aquí!

[una,si)[una,si]}r

.mePbrF – Full program with arguments a and b.
     rF – Fold by half-inclusive range. Yields the integers in [a, b).
.m      – Values b in that list which give minimal results when applied f.
  ePb   – function / block f. 
   Pb   – Prime factors of b.
  e     – Last element. This is guaranteed to yield the largest, as they're sorted.
Sr. Xcoder
fuente
1

Cobra - 150

def f(r as vari int)
    x,y=r
    c,o=y,0
    for n in x:y,for m in n:0:-1
        p=1
        for l in 2:m,if m%l<1,p=0
        if n%m<=0<p
            if m<c,c,o=m,n
            break
    print o

Ni siquiera estoy seguro de por qué me molesté, la cobra simplemente no puede competir aquí.

Οurous
fuente
1
Cobra se ve idéntico a Python ... ¿Cuáles son las diferencias?
Beta Decay
@BetaDecay Cobra es lo que sucede cuando le das a C # la sintaxis de Python. El sitio web de Cobra
Augurous
1

Ruby - 113 caracteres

Usando el stdlib. Devuelve un resultado. Probado en rubí 2.1.2.

require 'prime'
def smooth_range(a,b)
  (a...b).sort_by{|e|e.prime_division.flat_map{|f,p|[f]*p}.uniq.max}[0]
end
John P. Terry
fuente
1
Bienvenido a Programing Puzzles y Code Golf Stack Exchange. Gracias por publicar tu resultado. Como se trata de una pregunta de código de golf, incluya su recuento de caracteres en su respuesta. Puede usar una herramienta como esta: javascriptkit.com/script/script2/charcount.shtml
isaacg
1

Perl (5.10+), 83

for(<>..<>){$n=$_;$p=2;$_%$p&&$p++or$_/=$p while$_>1;$m=$p,$r=$n if$p<$m||!$m}
say$r

(se puede eliminar el salto de línea). Toma dos puntos finales de un rango inclusivo en dos líneas de stdin (porque <>es más barato que acceder ARGV) y genera el más suave para stdout. Si hay un empate para el más suave, imprime el más pequeño. Podría imprimir la más grande a costa de un personaje.

El algoritmo es básicamente la forma de Isaac de encontrar el mayor factor primo, aunque se nos ocurrió de forma independiente. Esa parte se reduce maravillosamente a una sola declaración en perl, el resto tiene más gastos generales de lo que me gustaría.

Debe ejecutarse debajo perl -Eo con un use 5.012preámbulo. Si no puede hacer eso, reemplácelo say$rcon print$r,$/.

hobbs
fuente
1

Pitón 2 (84)

f=lambda n,p=2:n>1and f(n/p**(n%p<1),p+(n%p>0))or p
print min(range(*input()),key=f)

La solución de @ isaacg , pero con una mintecla de función by en lugar de min- find explícito, y una función recursiva que desempeña el papel de la iteración.

Ejecute en Python apilable para evitar los límites de recursión.

Parece un desperdicio usar la condición paranthesized (n%p<1), luego repetir su negación también en paréntesis (n%p>0), pero eso fue lo mejor que obtuve. Intenté muchas cosas, pero resultaron peores.

f(n/p**(n%p<1),p+(n%p>0))     # Current for comparison
f(*[n/p,n,p,p+1][n%p>0::2])
n%p and f(n,p+1)or f(n/p,p)
f(*n%p and[n,p+1]or[n/p,p])

Agradezco cualquier mejora que se te ocurra.

xnor
fuente
1

Java 8 - 422 454 caracteres

Estoy aprendiendo Java 8, y quería darle una oportunidad a esto en relación con Java (o incluso secuencias de Java 8).

En comparación con otros idiomas, este es brutal pero un ejercicio interesante.

Golfizado:

import java.util.stream.*;import java.math.*;
class F{int v;int i;public int getV() { return v; }
F(int i){this.i = i;v=IntStream.range(2,i+1).map(j->((i%j==0)&&new BigInteger(""+j).isProbablePrime(1))?j:0).max().getAsInt();}}
public class T{
int s(int a, int b){return IntStream.range(a,b+1).boxed().map(F::new).sorted(java.util.Comparator.comparingInt(F::getV)).collect(java.util.stream.Collectors.toList()).get(0).i;}}

Sin golf:

import java.util.stream.*;
import java.math.*;

class F {
    int v;
    int i;
    public int getV() { return v; }
    F (int i) { 
        this.i = i;
        v = IntStream.range(2,i+1)
                     .map( j -> ((i%j==0) && 
                           new BigInteger(""+j).isProbablePrime(1))?j:0)
                     .max()
                     .getAsInt();
    }
}

public class T {
    int s(int a, int b) {
        return IntStream.range(a,b+1)
                    .boxed()
                    .map(F::new)
                    .sorted(java.util.Comparator.comparingInt(F::getV))
                    .collect(java.util.stream.Collectors.toList())
                    .get(0).i;
    }
}

ejemplo ejecutado usando:

public static void main(String[] s) {
    System.out.println(new T().s(157,249));
}

192
Michael Easter
fuente
1

MATL ( no competitivo ), 20 bytes

Este lenguaje fue diseñado después del desafío.

El alcance es inclusivo en ambos extremos. Los números se toman como dos entradas separadas.

2$:t[]w"@YfX>v]4#X<)

Pruébalo en línea!

Explicación

2$:          % implicitly input two numbers. Inclusive range
t            % duplicate                      
[]           % empty array
w            % swap elements in stack         
"            % for each                  
  @          %   push loop variable
  Yf         %   prime factors                  
  X>         %   maximum value
  v          %   vertical concatenation         
]            % end for each                         
4#X<         % arg min 
)            % index with this arg min into initial range of numbers
Luis Mendo
fuente
Supongo que hoy serían 17 bytes &:[]y"@YfX>h]&X<)o quizás 16 :[]y"@YfX>h]&X<). La &realidad era una gran idea (y supongo que yno estaba disponible en ese entonces?).
sundar
Y parece que la transmisión Yfcon 1 con prefijo también habría sido útil aquí, pero eso probablemente no sea suficiente para decidir que es una buena idea en general. :)
Sundar
Sí, este fue el comienzo, así que no yo &. Gracias a Suever por la semántica muy útil de este último (mi idea inicial fue hacer que significara "una entrada más que la predeterminada"). Si vemos más casos en los que Yfagregar útiles sería útil, realmente valdría la pena agregar esa característica. El problema es que hay alrededor de 34 respuestas que usan Yf(de acuerdo con este script ), por lo que es difícil saberlo
Luis Mendo
1

Jelly , 7 bytes, puntaje = 7 ÷ 7 × 8 = 8, desafío de fechas posteriores al idioma

rÆfṀ$ÐṂ

Pruébalo en línea!

Toma los puntos finales de rango inferior y superior como dos argumentos separados. Emite una lista de todos los números más suaves en el rango. (Esto se puede ver como una función, en cuyo caso el resultado es una lista Jelly, o como un programa completo, en cuyo caso el resultado utiliza la misma representación de lista que JSON).

Explicación

Esos momentos en que su programa Jelly es solo una traducción literal de la especificación ...

rÆfṀ$ÐṂ
r        Range from {first argument} to {second argument}
     ÐṂ  Return the elements which have the minimum
   Ṁ$      largest
 Æf          prime factor

fuente