Encontre a Raiz Quadrada

19

Escreva um código que, quando dado um número positivo como entrada, produz o maior divisor positivo de x menor ou igual à raiz quadrada de x .xxx

Em outras palavras, encontre o maior tal quen>0

mn:mn=x

(Existe maior ou igual a n, de modo que m vezes n é x )mnmnx


Por exemplo, se a entrada fosse os divisores serão 1 , 2 , 3 , 4 , 6 e 12 . 1 , 2 e 3 multiplicam-se por números maiores para obter 12 , mas como 3 é o maior, retornamos 3 .1212346121231233


Isso é então as respostas serão pontuadas em bytes, com menos bytes sendo considerados melhores.

Casos de teste

(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

Assistente de Trigo
fonte
11
Não vejo como o fechamento de perguntas populares, uma vez que bobagens de inativas mais antigas ajudam o site ...? Se você perceber cedo, com certeza, vá em frente e martele-o. Se tiver o dobro do número de respostas e mais votos positivos do que o antigo. Mantenha-o, e se alguma coisa, perto do outro ...
Stewie Griffin
@ StewieGriffin Um problema com as "perguntas populares" é que elas estão no HNQ. O que provavelmente não é uma coisa muito boa. / Também não vejo como isso prejudica o site, basta mover as respostas para a antiga.
user202729
5
O HNQ pode atrair novos usuários, e isso é uma coisa boa (IMO).
Stewie Griffin
1
@qwr Mas a idéia central é a mesma. A diferença é muito pequena. O método em cada desafio pode ser usado para outro.
user202729
1
@ Mão-E-Comida Não afirmo que este seja diferente. Na verdade, acredito que os dois tenham o mesmo conteúdo. Minhas razões para o fechamento da sua pergunta são as mesmas do comentário na parte superior do tópico, esta pergunta tem mais respostas. A meta está aqui, se você gostaria de perguntar lá. Você também pode ter interesse nisso .
Assistente de trigo

Respostas:

10

Python3 , 49 47 bytes

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

Explicação

  • l=x**.5//1→ Atribua lo maior número inteiro menor que igual à raiz quadrada dex
  • while x%l:l-=1→ Embora lnão se divida uniformemente x, diminua l.

Editar% s

  • Mencione Python3, não Python2
  • Use ...//1para salvar dois bytes. (Decimais estão bem! Obrigado @Rod)
voluntário
fonte
Bem-vindo ao PPCG, boa primeira resposta! Você pode salvar alguns bytes usando input/ em printvez de def/ return, também pode substituir int(...)por ...//1para salvar mais bytes, como você pode ver aqui #
207 Rod Rod
@ Rod não // 1, como eu quis dizer, disse Python3. (A menos que decimais sejam aceitáveis ​​para a saída, o que eu acho que não.) Mas para o Python2, obrigado!
hunteke
@hunteke A saída decimal é boa, não vejo motivo para não ser.
Assistente de trigo
Seria mais curto com "For" em vez de "While", para que você possa atribuir valores na condicional, possivelmente evitando definir "l"?
Malady 21/06
8

MATL , 7 bytes

Z\tn2/)

Experimente online!

Para esta explicação, usaremos '12' como uma entrada de amostra. Explicação:

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

Isso funciona devido a muitas coincidências de sorte.

  1. MATL usa 1 indexação
  2. Se indexarmos com um não inteiro (isso acontecerá para qualquer entrada quadrada perfeita), <n>)indexaremosn
DJMcMayhem
fonte
1
...... bem, eu fui derrotado!
21418 Giuseppe #:
Tinha que ser você quem respondeu isso em MATL :-)
Luis Mendo
BTW eu acho que você pode encurtar a Z\J2/)( J2/ou equivalentemente .5jsignifica end/2quando usado como um índice)
Luis Mendo
Pode valer a pena explicar o comportamento quando aplicado a um número com um número ímpar de divisores, pois "Índice" com um valor não inteiro não é óbvio.
21418 Kamil Drakari
@KamilDrakari Como é isso?
DJMcMayhem
7

C (gcc) -lm , 35 bytes

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

Experimente online!

cleblanc
fonte
2
BTW, isso só funciona por causa do reconhecimento do GCC sqrtcomo uma função interna. Com -fno-builtin-sqrt, o gcc assume int sqrt(int)e não passa a double. Em x86-64, doubleé passado em um registro diferente de um número inteiro. Em 32 bits, um doublelevaria 2 slots na pilha, então você também passaria lixo (ou um subnormal com o número inteiro como parte inferior da mantissa, se os 32 bits superiores fossem zero). Isso também é interrompido, a menos que você esteja fazendo uma compilação de depuração, porque se baseia no código-gen não otimizado padrão de avaliação de expressões do gcc no registro de valor de retorno.
22818 Peter Cordes
@PeterCordes Sim, é golf código, não um dispositivo médico :-)
cleblanc
Bem, eu não sou fã do truque de retorno falso. Isso nem é mais C, é apenas um detalhe de implementação com uma configuração de compilador que é o padrão. (. É realmente esticar o "tem que trabalhar com pelo menos uma implementação" regra) A sqrt()questão é diferente: eu estava curioso para saber como que conseguiu trabalho, porque o chamador tem que de alguma forma sabe converter intpara double. Eu postei a resposta para isso como um comentário, caso alguém mais estivesse curioso. Efetivamente gcc tem sqrt(incluindo protótipo) como um built-in, caso contrário, este seria um fracasso por razões às vezes vemos no SO asm Qs
Peter Cordes
i;f(n){for(i=0;++i<n/i||n%i;);}é 31B e funciona com gcc -Ox86-64 (custando 2 ou 3 bytes a mais para a opção de linha de comando.) Usar em ||vez de |faz com que o gcc deixe o n/iresultado idivno EAX, o registro de valor de retorno ( godbolt.org/g/RJYeui ) O comportamento indefinido de ++isem um ponto de sequência funciona. (O asm produzido é basicamente o mesmo que a minha resposta código de máquina x86 ). Com -O0, gcc sempre parece deixar iem EAX, mas talvez possamos usar isso ...
Peter Cordes
De qualquer forma, se você gosta de respostas que não sejam de C gcc, talvez goste desta resposta x86-64 gcc que funciona por causa do ASM produzido pelo compilador para um comportamento claramente indefinido: Experimente on-line! (31 + 2 bytes)
Peter Cordes
5

05AB1E , 5 bytes

Ñ2äнθ

Experimente online! ou como um conjunto de testes

Explicação

Ñ        # push the list of divisors
 2ä      # split it into 2 parts
   н     # take the first haft
    θ    # take the last element of that
Emigna
fonte
5

APL (Dyalog Unicode) , 16 14 12 bytes

Fico feliz por ter conseguido escrever alguma resposta no APL, pois apenas o aprendi. Muito, muito obrigado a Adám pela ajuda no golfe. Sugestões de golfe muito bem-vindas.Experimente online!

Para saber mais sobre o APL, dê uma olhada no The APL Orchard .

EDIT: -2 bytes para corrigir um problema com o meu código. Agradecemos a H.PWiz por apontar esse problema. -2 bytes de encurtar tudo novamente.

⌈/{⍳⌊⍵*÷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
fonte
Por que você raspa em ordem inversa? ... Muitas vezes vejo --- 16 --- --- 14 --- 12, não 12 --- 14 --- --- 16 ---.
user202729
@ user202729 Sinceramente, já faz um tempo, e eu esqueci bastante a ordem do tachado. Irá corrigir isso em breve.
Sherlock9
Na verdade, não é um problema, o snippet da tabela de classificação suporta ambos.
user202729
4

Casca , 4 bytes

→←½Ḋ

Experimente online!

Explicação

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

fonte
3

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

changelog: manipule o n=1caso de teste corretamente, salve 2 bytes e retorne no EAX.

Conte até n/i <= i(ou seja, quando atingirmos o sqrt) e use o primeiro divisor exato depois disso.

Uma versão de 64 bits pode ser chamada de C com a convenção de chamada do System 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

Experimente online! com um chamador asm que usa o primeiro byte de argv [1] como um número inteiro diretamente e usa o resultado como status de saída do processo.

$ 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
fonte
1
Tem certeza de que n = 1 não é apenas 1? Ele é listado como um caso de teste e é um divisor ≤ √1 = 1.
QWR
Sua resposta deve funcionar para 1. Se não funcionar com o seu algoritmo, você precisará codificá-lo.
Wheat Wizard
2
@qwr: atualizado com uma versão mais curta que funciona para todas as entradas.
Peter Cordes
2

Japonês -h, 8 6 bytes

â f§U¬

Tente

2 bytes salvos graças a Oliver


Explicação

           :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
Shaggy
fonte
Os sinalizadores ainda não custam bytes?
mbomb007
@ mbomb007 Não. Cada instância de um sinalizador é considerada uma nova entrada de idioma.
Oliver
Deixa pra lá. Acho que ainda não tinha visto essa meta post .
mbomb007
2

Boneco de neve , 38 bytes

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

Experimente online!

((
  }        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
))
Maçaneta da porta
fonte
2

dc , 24

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

Experimente online!

Explicação:

?                         # 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
fonte
2

J, 24 19 bytes

-5 bytes graças à ideia GCD de Sherlock

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

Experimente online!

resposta original

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

Experimente online!

analisado

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

explicação

  • 1 + i.@<.@%:dá o intervalo 1 .. floor(sqrt).
  • o verbo inteiro (A) Bforma um gancho, com o intervalo acima passado como o argumento da direita ]para A e o número original como o argumento da esquerda [. Portanto...
  • ] | [ fornece o restante de cada item no intervalo dividido no argumento original.
  • e 0 = ] | [fornece os divisores sem resto.
  • ] #~ ... depois filtra o intervalo, deixando apenas esses.
  • e {:fornece o último item da lista, ou seja, o maior.
Jonah
fonte
1

Haskell , 36 bytes

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

Experimente online!

Bem, esta é a minha resposta para este desafio. Isso usa uma compreensão específica da lista para encontrar a resposta. Em nossa compreensão de lista, escolhemosyda lista infinita [1..]que é os números inteiros positivos, e escolhemoszda lista [1..y]. Isso significa que(y,z) são todos os pares ordenados, de modo que yz.

Em seguida, selecionamos apenas os pares de modo que yz=x, o que significa que fazemos a lista de todos os pares de números que se multiplicam para x. Agora, já que nossa compreensão é baseada primeiro emy e depois z isso significa que nossos pares estão em ordem crescente de y, ou mais útil em ordem decrescente de z.

Então, para obter o maior z nós pegamos o zpertencente ao primeiro elemento. Este é o nosso resultado.

Assistente de Trigo
fonte
1

QBasic (4.5), 52 bytes

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

Quarto (gforth) , 53 bytes

A maneira mais curta parece estar usando a pilha de ponto flutuante e fsqrt, a menor possível sem 62 bytes /mode usando e verificando se o quociente era maior que o divisor.

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

Experimente online!

Explicação

  1. Calcular a raiz quadrada
  2. Começando pela raiz quadrada, diminua 1 até encontrarmos um fator do número original

Código Explicação

: 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
fonte
1

F #, 55 49 bytes

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

Experimente online!

Seq.findBack: Retorna o último elemento para o qual a função especificada retorna True. A função neste caso verifica se um número é um fator do valor.

Ciaran_McCarthy
fonte
1

Flacidez cerebral , 144 bytes

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

Experimente online!

Não tenho certeza se essa resposta é muito boa. Sinto que pode haver uma boa maneira de resolver essa tarefa, mas não sou inteligente o suficiente.

Explicação

Tentei fazer uma visão detalhada da resposta, mas há tantas partes móveis que não foram muito esclarecedoras, então aqui está uma explicação do que o código faz.

A primeira parte importante é essa

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

Isso pega os dois números no topo da pilha e, se forem desiguais, incrementa o segundo, se forem iguais, incrementa o primeiro e substitui o segundo por zero. Se repetirmos esse código várias vezes, obteremos todos os pares(x,y) de tal modo que xy.

A próxima parte é a multiplicação, tirada com modificação do wiki . Essa multiplicação é especial porque preserva os valores existentes sem destruí-los. É assim:

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

Então, nós estamos multiplicando todos esses pares ordenados. Para cada resultado, verificamos se é igual à entrada. Nesse caso, encerramos e devolvemos o item menor do par.

Assistente de Trigo
fonte
0

Jelly, 6 bytes

ÆDŒHḢṪ

Try it online!

Erik the Outgolfer
fonte
0

Rust, 71 70 bytes

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

Pre-uglified version

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
}

Edits

  • Save a byte with > 0 over != 0. (Thanks to @CatWizard)
hunteke
fonte
Can != be replaced with >?
Wheat Wizard
Good call! Yes.
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)))}

You can try this online by copying it into the online Pyret editor!

The above evaluates to an anonymous function. When it is applied to an integer, it returns a result according to the specification.

Tango
fonte
0

Actually, 7 bytes

Based on my APL answer here. Golfing suggestions welcome! Try it online!

;√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
fonte
0

A port of this Mathematica answer.

Jelly, 11 bytes

½ðḞ³÷Ċ³÷µÐL

Try it online!

This (11 bytes) also works, and don't depend on ³:

½Ḟ÷@Ċ÷@ʋƬµṪ

Unfortunately ½Ḟ÷@Ċ÷@ʋÐL (10 bytes) doesn't work. And apparently Ƭ and ÐĿ is not exactly the same (when the link is dyadic)


Method: (let n be the input)

  • Start with an upper bound i=n of the answer a.
  • At each step:
    • If i is not an integer, then the upper bound can be made i (because the result must be an integer)
    • If ni is not an integer, then ainaninanian÷ni.
  • So we repeatedly replace i with n÷ni until it's fixed.
user202729
fonte
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 answer.

Try it online.


Old 65 bytes answer:

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

Try it online.

Explanation:

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
fonte