Encuentra la raíz cuadrada

19

Escriba el código que cuando se le da un número positivo como entrada, genera el mayor divisor positivo de menor o igual que la raíz cuadrada de x .xxx

En otras palabras, encuentre el n> 0 más grande de n>0manera

mn:mn=x

(Existe m mayor que o igual a n tales que m veces n es x )


Por ejemplo, si la entrada fuera 12 los divisores son 1 , 2 , 3 , 4 , 6 y 12 . 1 , 2 y 3 multiplican por números más grandes para obtener 12 , pero 3 es el más grande, por lo que devolvemos 3 .


Este es el por lo que las respuestas se puntuarán en bytes, con menos bytes que se consideren una mejor puntuación.

Casos de prueba

(1,1)
(2,1)
(3,1)
(4,2)
(5,1)
(6,2)
(7,1)
(8,2)
(9,3)
(10,2)
(11,1)
(12,3)
(13,1)
(14,2)
(15,3)
(16,4)
(17,1)
(18,3)
(19,1)
(20,4)
(21,3)
(22,2)
(23,1)
(24,4)
(25,5)
(26,2)
(27,3)
(28,4)
(29,1)
(30,5)
(31,1)
(32,4)
(33,3)
(34,2)
(35,5)
(36,6)
(37,1)
(38,2)
(39,3)
(40,5)
(41,1)
(42,6)
(43,1)
(44,4)
(45,5)
(46,2)
(47,1)
(48,6)
(49,7)
(50,5)

OEIS A033676

Asistente de trigo
fuente
11
No veo cómo el cierre de preguntas populares como engaños de personas inactivas mayores ayuda al sitio ... Si lo notas temprano, seguro, adelante y martillo. Si tiene el doble de respuestas y más votos positivos que el anterior. Guárdelo y, si algo, cierre el otro ...
Stewie Griffin
@StewieGriffin Un problema con las "preguntas populares" es que están en HNQ. Lo cual probablemente no sea algo muy bueno. / No veo cómo daña el sitio tampoco, solo puedes mover las respuestas a la anterior.
user202729
55
El HNQ podría atraer a nuevos usuarios, y eso es algo bueno (IMO).
Stewie Griffin
1
@qwr Pero la idea central es la misma. La diferencia es muy pequeña. El método en cada desafío se puede usar para otro.
user202729
1
@ Hand-E-Food No digo que este sea diferente. De hecho, creo que los dos tienen el mismo contenido. Mis razones para el cierre de su pregunta son las mismas que las del comentario en la parte superior del hilo, esta pregunta tiene más respuestas. El meta está aquí si desea preguntar allí. También puede tener interés en esto .
Wheat Wizard

Respuestas:

10

Python3 , 49 47 bytes

def f(x):
 l=x**.5//1
 while x%l:l-=1
 return l

Explicación

  • l=x**.5//1→ Asigne lel entero más grande menor que igual a la raíz cuadrada dex
  • while x%l:l-=1→ Mientras lno se divide equitativamente x, decremente l.

Ediciones

  • Mencione Python3, no Python2
  • Use ...//1para guardar dos bytes. (¡Los decimales están bien! Gracias @ Rod)
Hunteke
fuente
Bienvenido a PPCG, buena primera respuesta! Usted puede ahorrar unos pocos bytes utilizando input/ printlugar def/ return, también puede reemplazar int(...)con ...//1ahorrar más bytes como se puede ver aquí
Varilla
@ Rod no // 1, como quise decir, he dicho Python3. (A menos que los decimales estén bien para la salida, lo cual no creo). Pero para Python2, ¡gracias!
hunteke
@hunteke La salida decimal está bien, no veo ninguna razón por la que no debería estarlo.
Wheat Wizard
¿Sería más corto con "For" en lugar de "While", para que pueda asignar valores en el condicional, posiblemente evitando definir "l"?
Malady
8

MATL , 7 bytes

Z\tn2/)

Pruébalo en línea!

Para esta explicación, utilizaremos '12' como entrada de muestra. Explicación:

Z\      % Divisors.
        % Stack:
        %   [1 2 3 4 6 12]
  t     % Duplicate.
        % Stack:
        %   [1 2 3 4 6 12]
        %   [1 2 3 4 6 12]
   n    % Number of elements.
        % Stack:
        %   6
        %   [1 2 3 4 6 12]
    2/  % Divide by 2
        % Stack:
        %   3
        %   [1 2 3 4 6 12]
      ) % Index (grab the 3rd element)
        % 3

Esto funciona debido a muchas coincidencias afortunadas.

  1. MATL usa 1 indexación
  2. Si indexamos con un no entero (esto sucederá para cualquier entrada cuadrada perfecta), entonces <n>)indexará norte
DJMcMayhem
fuente
1
...... bueno, ¡he sido completamente derrotado!
Giuseppe
Debiste ser tú quien respondió esto en MATL :-)
Luis Mendo
Por cierto, creo que puede acortar Z\J2/)( J2/o .5jsignifica equivalente end/2cuando se usa como índice)
Luis Mendo
Puede valer la pena explicar el comportamiento cuando se aplica a un número con un número impar de divisores, ya que "Índice" con un valor no entero no es obvio.
Kamil Drakari
@KamilDrakari ¿Cómo es eso?
DJMcMayhem
7

C (gcc) -lm , 35 bytes

i;f(n){for(i=sqrt(n);n%i;i--);n=i;}

Pruébalo en línea!

cleblanc
fuente
2
Por cierto, esto solo funciona debido al reconocimiento de GCC de sqrtcomo una función incorporada. Con -fno-builtin-sqrt, gcc asume int sqrt(int), y no pasa a double. En x86-64, doublese pasa en un registro diferente que un entero. En 32 bits, a doubleocuparía 2 ranuras en la pila, por lo que también pasaría basura (o una subnormal con el entero como la parte inferior de la mantisa, si los 32 bits superiores fueran cero). Esto también se rompe a menos que esté realizando una compilación de depuración porque se basa en el código gen-gen no optimizado predeterminado de gcc para evaluar expresiones en el registro de valor de retorno.
Peter Cordes
@PeterCordes Sí, es código golf, no un dispositivo médico :-)
cleblanc
Bueno, no soy fanático del hack de retorno falso. Eso ya ni siquiera es C, es solo un detalle de implementación con una configuración de compilador que resulta ser la predeterminada. (. Es realmente estirar el "tiene que trabajar con al menos una aplicación" regla) El sqrt()tema es diferente: tenía curiosidad cómo conseguido trabajo, porque la persona que llama tiene que saber de alguna manera para convertir inta double. Publiqué la respuesta a eso como un comentario en caso de que alguien más tuviera curiosidad. Efectivamente, gcc tiene sqrt(incluido el prototipo) como incorporado, de lo contrario, esto fallaría por razones que a veces vemos en SO asm Qs
Peter Cordes
i;f(n){for(i=0;++i<n/i||n%i;);}es 31B y funciona con gcc -Ox86-64 (cuesta 2 o 3 bytes más para la opción de línea de comando). En ||lugar de hacer |que gcc deje el n/iresultado idiven EAX, el registro de valor de retorno ( godbolt.org/g/RJYeui ) El comportamiento indefinido ++isin un punto de secuencia funciona. (El asm producido es básicamente el mismo que mi respuesta de código de máquina x86 .) Con -O0, gcc siempre parece salir ien EAX, pero tal vez podamos usar eso ...
Peter Cordes
De todos modos, si le gustan las respuestas de detalles de implementación de gcc que no son C, tal vez le guste esta respuesta de gcc x86-64 que funciona debido a los asm producidos por el compilador para un comportamiento claramente indefinido: ¡ Pruébelo en línea! (31 + 2 bytes)
Peter Cordes
5

APL (Dyalog Unicode) , 16 14 12 bytes

Me alegro de haber podido escribir alguna respuesta en APL ya que solo la aprendí. Muchas, muchas gracias a Adám por su ayuda con el golf. Sugerencias de golf muy bienvenidas. Pruébalo en línea!

Para obtener más información sobre APL, eche un vistazo a The APL Orchard .

EDITAR: -2 bytes para solucionar un problema con mi código. Gracias a H.PWiz por señalar ese problema. -2 bytes de acortar todo de nuevo.

⌈/{⍳⌊⍵*÷2}∨⊢

Ungolfing

⌈/{⍳⌊⍵*÷2}∨⊢
             GCD of the following...
               The right argument, our input.
  {⍳⌊⍵*÷2}
                 Our input.
      2         To the power of 1/2, i.e. square root.
                 Floor.
                 Indices up to floor(sqrt(input)).
                In total, range from 1 to floor(sqrt(input)).
⌈/            The maximum of the GCDs of our input with the above range.
Sherlock9
fuente
¿Por qué tacha en orden inverso? ... A menudo veo --- 16 --- --- 14 --- 12, no 12 --- 14 --- --- 16 ---.
user202729
@ user202729 Francamente, ha pasado un tiempo y olvidé por completo el orden de tachado. Lo arreglará en breve.
Sherlock9
En realidad no es un problema, el fragmento de la tabla de clasificación es compatible con ambos.
user202729
4

Casco , 4 bytes

→←½Ḋ

Pruébalo en línea!

Explicación

→←½Ḋ
   Ḋ      Divisors of (implicit) input.
  ½       Bisect.
→←        Take the last element of the first half.

fuente
3

Código de máquina x86 de 32 bits (IA32): 18 16 bytes

registro de cambios: maneje el n=1caso de prueba correctamente, guarde 2 bytes y regrese en EAX.

Cuente hasta n/i <= i(es decir, cuando alcancemos el sqrt), y use el primer divisor exacto después de eso.

Una versión de 64 bits de esto es invocable desde C con la convención de llamadas del sistema V x86-64, como
int squarish_root_countup(int edi).

nasm -felf32 -l/dev/stdout squarish-root.asm:

58                         DEF(squarish_root_countup)
59                             ; input: n in EDI
60                             ; output: EAX
61                             ; clobbers: eax,ecx,edx
62                         .start:
63 00000025 31C9               xor    ecx, ecx
64                         .loop:                    ; do{
65                         
66 00000027 41                 inc    ecx                ; ++i
67 00000028 89F8               mov    eax, edi
68 0000002A 99                 cdq
69 0000002B F7F9               idiv   ecx                ; edx=n%i    eax=n/i
70                         
71 0000002D 39C1               cmp    ecx, eax
72 0000002F 7CF6               jl     .loop          ; }while(i < n/i
73                                                   ;          || n%i != 0);  // checked below
74                             ; falls through for i >= sqrt(n)
75                             ; so quotient <= sqrt(n) if we get here
76                         
77                                                   ; test edx,edx / jnz  .loop
78 00000031 4A                 dec    edx            ; edx-1 is negative only if edx was zero to start with
79 00000032 7DF3               jge   .loop           ; }while(n%i >= 1);
80                             ; falls through for exact divisors
81                         
82                             ; return value = quotient in EAX
83                         
84 00000034 C3                 ret

           0x10 bytes = 16 bytes.

85 00000035 10             .size: db $ - .start

Pruébalo en línea! con una llamada asm que usa el primer byte de argv [1] como un entero directamente, y usa el resultado como estado de salida del proceso.

$ asm-link -m32 -Gd squarish-root.asm && 
for i in {0..2}{{0..9},{a..f}};do 
    printf "%d   " "0x$i"; ./squarish-root "$(printf '%b' '\x'$i)"; echo $?;
done

0   0  # bash: warning: command substitution: ignored null byte in input
1   1
2   1
3   1
4   2
5   1
6   2
7   1
8   2
9   3
10   0       # this is a testing glitch: bash ate the newline so we got an empty string.  Actual result is 2 for n=10
11   1
12   3
13   1
14   2
15   3
16   4
   ...
Peter Cordes
fuente
1
¿Estás seguro de que n = 1 no es solo 1? Está listado como un caso de prueba y es un divisor ≤ √1 = 1.
qwr
Su respuesta debería funcionar para 1. Si no funciona con su algoritmo, entonces tendrá que codificarlo.
Wheat Wizard
2
@qwr: actualizado con una versión más corta que funciona para todas las entradas.
Peter Cordes
2

Japt -h, 8 6 bytes

â f§U¬

Intentalo

2 bytes guardados gracias a Oliver


Explicación

           :Implicit input of integer U
â          :Divisors of U
  f        :Filter
   §       :  Less than or equal to
    U¬     :  Square root of U
           :Implicitly get the last element in the array and output it
Lanudo
fuente
¿Las banderas todavía no cuestan bytes?
mbomb007
@ mbomb007 No. Cada instancia de una bandera se considera una nueva entrada de idioma.
Oliver
No importa. Supongo que aún no había visto esa meta publicación .
mbomb007
2

Muñeco de nieve , 38 bytes

((}1vn2nD`#nPnF|:|NdE|;:,#NMo*|,;bW*))

Pruébalo en línea!

((
  }        activate variables b, e, and g
  1vn2nD`  e=1/2
  #        retrieve the input into b
  nP       set b=b^e, which is sqrt(input)
  nF       floor the square root
  |        move b into g so there's space for a while loop
  :        body of the loop
    |NdE|  decrement the value in g
  ;:       loop condition
    ,#     assign b=input, e=current value
    NMo    store the modulo in g
    *|     discard the input value and place the modulo in the condition slot
    ,      put the current value back into g
  ;bW      continue looping while the modulo is nonzero
  *        return the result
))
Pomo de la puerta
fuente
2

dc , 24

?dsnv1+[1-dlnr%0<m]dsmxp

Pruébalo en línea!

Explicación:

?                         # read input
 d                        # duplicate
  sn                      # store copy 1 in register n
    v                     # take the square root of copy 2
     1+                   # add 1
       [          ]       # define macro to:
        1-                #   subtract 1
          d               #   duplicate
           ln             #   load from register n
             r            #   reverse top 2 stack members
              %           #   calculate modulo
               0<m        #   if not 0, recursively call macro m again
                   d      # duplicate macro
                    sm    # store copy 1 in register m
                      x   # execute copy 2
                       p  # print final value
Trauma digital
fuente
2

J, 24 19 bytes

-5 bytes gracias a la idea GCD de Sherlock

([:>./+.)1+i.@<.@%:

Pruébalo en línea!

respuesta original

([:{:]#~0=]|[)1+i.@<.@%:

Pruébalo en línea!

analizado

┌───────────────────────────────┬──────────────────────┐
│┌──┬──┬───────────────────────┐│┌─┬─┬────────────────┐│
││[:│{:│┌─┬─────┬─────────────┐│││1│+│┌─────────┬─┬──┐││
││  │  ││]│┌─┬─┐│┌─┬─┬───────┐││││ │ ││┌──┬─┬──┐│@│%:│││
││  │  ││ ││#│~│││0│=│┌─┬─┬─┐│││││ │ │││i.│@│<.││ │  │││
││  │  ││ │└─┴─┘││ │ ││]│|│[││││││ │ ││└──┴─┴──┘│ │  │││
││  │  ││ │     ││ │ │└─┴─┴─┘│││││ │ │└─────────┴─┴──┘││
││  │  ││ │     │└─┴─┴───────┘│││└─┴─┴────────────────┘│
││  │  │└─┴─────┴─────────────┘││                      │
│└──┴──┴───────────────────────┘│                      │
└───────────────────────────────┴──────────────────────┘

explicación

  • 1 + i.@<.@%:da el rango 1 .. floor(sqrt).
  • todo el verbo (A) Bforma un gancho, con el rango anterior pasado como el argumento derecho ]a A y el número original pasado como su argumento izquierdo [. Así...
  • ] | [ da el resto de cada elemento en el rango dividido en el argumento original.
  • y 0 = ] | [le da a los divisores sin resto.
  • ] #~ ... luego filtra el rango, dejando solo esos.
  • y {:da el último elemento de la lista, es decir, el más grande.
Jonás
fuente
1

Haskell , 36 bytes

f x=[z|y<-[1..],z<-[1..y],y*z==x]!!0

Pruébalo en línea!

y[1..]z[1..y](y,z)yz

yz=XXyzyz

zz

Asistente de trigo
fuente
1

QBasic (4.5), 52 bytes

INPUT x
FOR i=1TO sqr(x)
if x/i=x\i then m=i
next
?m
Steenbergh
fuente
1

Adelante (gforth) , 53 bytes

La forma más corta parece estar usando la pila de punto flotante y fsqrt, la más corta que pude obtener sin ella fue 62 bytes usando /mody comprobando si el cociente era mayor que el divisor.

: f dup s>f fsqrt f>s 1+ begin 1- 2dup mod 0= until ;

Pruébalo en línea!

Explicación

  1. Calcule la raíz cuadrada
  2. Comenzando en la raíz cuadrada, disminuya en 1 hasta que encontremos un factor del número original

Explicación del código

: f                \ Start a word definition
dup                \ duplicate the input
s>f fsqrt          \ move the number to the float stack and get the square root
f>s                \ truncate result and move to integer stack
1+                 \ add 1 to the square root
begin              \ start indefinite loop
  1- 2dup          \ decrement divisor and duplicate input and divisor
  mod              \ calculate n % divisor
0= until           \ if result equals 0 (no remainder) end the loop
;                  \ end the word definition
reffu
fuente
1

F #, 55 49 bytes

let f x=Seq.findBack(fun i->x%i=0.0){1.0..x**0.5}

Pruébalo en línea!

Seq.findBack: Devuelve el último elemento para el que devuelve la función dada True. La función en este caso verifica si un número es un factor del valor.

Ciaran_McCarthy
fuente
1

Brain-Flak , 144 bytes

{({}{}<<>({}<>)<>([({})()]<>({}(<>)())){(<{}({}[()]{}<({}())>)>)}{}((({}<>)<>(({})))[({}[{}])])>[({<({}[()])><>({})<>}{}<><{}>)])}{}{}<>{}({}<>)

Pruébalo en línea!

No estoy realmente seguro de que esta respuesta sea muy buena. Siento que puede haber una buena manera de resolver esta tarea, pero no soy lo suficientemente inteligente.

Explicación

Traté de hacer una vista ampliada de la respuesta, pero hay tantas partes móviles que no fue muy esclarecedora, así que aquí hay una explicación de lo que hace el código.

El primer bit importante es este

({}<>)<>([({})()]<>({}(<>)())){(<{}({}[()]{}<({}())>)>)}{}

(X,y)Xy

La siguiente parte es la multiplicación, tomada con modificación de la wiki . Esta multiplicación es especial porque conserva los valores existentes sin destruirlos. Va como:

((({}<>)<>(({})))[({}[{}])])({<({}[()])><>({})<>}{}<><{}>)

Entonces estamos multiplicando todos estos pares ordenados. Para cada resultado verificamos si es igual a la entrada. Si es así, terminamos y devolvemos el artículo más pequeño en el par.

Asistente de trigo
fuente
0

Óxido, 71 70 bytes

fn f(x:u64)->u64{let mut l=(x as f64).sqrt()as u64;while x%l>0{l-=1}l}

Versión pre-uglified

fn f(x: u64) -> u64 {                    // function takes u64, gives u64
  let mut l = (x as f64).sqrt() as u64;  // l takes integer'ed root value
  while x % l > 0 {                      // loop while l leaves remainder
    l -= 1                               // decrement
  }
  l                                      // return the found value
}

Ediciones

  • Guardar un byte con > 0más != 0. (Gracias a @CatWizard)
Hunteke
fuente
Se !=puede reemplazar con >?
Wheat Wizard
¡Buena llamada! Si.
hunteke
0

Pyret , 93 bytes

{(z):rec f={(i,x):if num-modulo(i, x) == 0:x else:f(i,x - 1)end}
f(z,num-floor(num-sqrt(z)))}

¡Puede probar esto en línea copiándolo en el editor de Pyret en línea !

Lo anterior se evalúa como una función anónima. Cuando se aplica a un entero, devuelve un resultado de acuerdo con la especificación.

Tango
fuente
0

En realidad , 7 bytes

Basado en mi respuesta APL aquí . Sugerencias de golf bienvenidas! Pruébalo en línea!

;√LR♀gM

Ungolfing

;√LR♀gM  Implicit input n
;        Duplicate n
 √       sqrt(n)
  L      floor(sqrt(n))
   R     1..floor(sqrt(n))
    ♀g   gcd(n, foreach(1..floor(sqrt(n)))
      M  The maximum of the GCDs.
         Return this maximum.
Sherlock9
fuente
0

Un puerto de esta respuesta de Mathematica .

Jalea , 11 bytes

½ðḞ³÷Ċ³÷µÐL

Pruébalo en línea!

Esto (11 bytes) también funciona y no depende de ³:

½Ḟ÷@Ċ÷@ʋƬµṪ

Lamentablemente ½Ḟ÷@Ċ÷@ʋÐL(10 bytes) no funciona. Y aparentemente Ƭy ÐĿno es exactamente lo mismo (cuando el enlace es diádico)


Método: (let norte ser la entrada)

  • Comience con un límite superior yo=norte de la respuesta un.
  • En cada paso:
    • Si yo no es un entero, entonces se puede hacer el límite superior yo (porque el resultado debe ser un entero)
    • Si norteyo no es un entero, entonces unyonorteunnorteyonorteunnorteyounnorte÷norteyo.
  • Así que reemplazamos repetidamente yo con norte÷norteyo hasta que se arregle.
usuario202729
fuente
0

Java 8, 65 54 bytes

n->{int r=(int)Math.sqrt(n);for(;n%r>0;r--);return r;}

Port of @hunteke 's Python 3 respuesta .

Pruébalo en línea.


Antigua respuesta de 65 bytes:

n->{int r=1,i=n;for(;i-->1;)r=n%i<1&n/i<=i&n/i>r?n/i:r;return r;}

Pruébalo en línea.

Explicación:

n->{                // Method with integer as both parameter and return-type
  int r=1,          //  Result-integer, starting at 1
  i=n;for(;i-->1;)  //  Loop `i` in the range (n, 1]
    r=n%i<1         //   If `n` is divisible by `i`,
      &n/i<=i       //   and if `n` divided by `i` is smaller than or equal to `i` itself,
      &n/i>r?       //   and if `n` divided by `i` is larger than the current `r`
       n/i          //    Set `n` divided by `i` as the new result `r`
      :             //   Else:
       r;           //    Leave result `r` unchanged
  return r;}        //  Return the result `r`
Kevin Cruijssen
fuente