Znajdź Squarish Root

19

Napisz kod, który po podaniu liczby dodatniej jako wartości wyjściowej wyprowadza największy dodatni dzielnik mniejszy lub równy pierwiastkowi kwadratowemu z .x xxxx

Innymi słowy, znajdź największą taką, żen>0

mn:mn=x

(Występuje większe lub równe tak, że razy jest )n m n xmnmnx


Na przykład, jeśli dane wejściowe wynosiły dzielnikami są , , , , i . , i wszystkie mnożą się przez większe liczby, aby uzyskać , ale jest największym, więc zwracamy .1 21212346121231233


To jest więc odpowiedzi będą oceniane w bajtach, a mniej bajtów będzie uważanych za lepszy wynik.

Przypadki testowe

(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

Kreator pszenicy
źródło
11
Nie rozumiem, w jaki sposób zamykanie popularnych pytań jako duplikatów starszych nieaktywnych pomaga stronie ...? Jeśli zauważysz to wcześnie, jasne, śmiało. Jeśli ma dwa razy więcej odpowiedzi i więcej głosów pozytywnych niż poprzednia. Zachowaj, a jeśli już, zamknij drugi ...
Stewie Griffin
@StewieGriffin Problem z „popularnymi pytaniami” polega na tym, że są na HNQ. Co prawdopodobnie nie jest zbyt dobrą rzeczą. / Nie widzę też, jak szkodzi stronie, możesz po prostu przenieść odpowiedzi na starą.
user202729,
5
HNQ może przyciągnąć nowych użytkowników, i to dobrze (IMO).
Stewie Griffin
1
@qwr Ale podstawowa idea jest taka sama. Różnica jest bardzo mała. Metodę w każdym wyzwaniu można zastosować do innego.
user202729,
1
@ Hand-E-Food Nie twierdzę, że ten jest inny. W rzeczywistości uważam, że oba mają tę samą treść. Moje powody zamknięcia twojego pytania są takie same jak w komentarzu na górze wątku, to pytanie ma więcej odpowiedzi. Meta jest tutaj, jeśli chcesz tam zapytać. Można również mieć interes w tym .
Wheat Wizard

Odpowiedzi:

10

Python3 , 49 47 bajtów

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

Wyjaśnienie

  • l=x**.5//1→ Przypisz lnajwiększą liczbę całkowitą mniejszą niż pierwiastek kwadratowy zx
  • while x%l:l-=1→ Chociaż lnie dzieli się równomiernie x, zmniejsza się l.

Edycje

  • Wspomnij o Python3, a nie Python2
  • Użyj, ...//1aby zapisać dwa bajty. (Dziesiętne są w porządku! Dzięki @Rod)
hunteke
źródło
Witamy w PPCG, fajna pierwsza odpowiedź! Można zaoszczędzić kilka bajtów za pomocą input/ printzamiast def/ returnmożna również wymienić int(...)się ...//1uratować więcej bajtów jak widać tutaj
Rod
@Rod nie // 1, jak miałem na myśli powiedział Python3. (Chyba że dziesiętne są odpowiednie dla danych wyjściowych, co nie wydaje mi się.) Ale dla Python2, dzięki!
hunteke
@hunteke Wyjście dziesiętne jest w porządku, nie widzę żadnego powodu, dla którego nie powinno być.
Wheat Wizard
Czy byłby krótszy z „For” zamiast „While”, abyś mógł przypisywać wartości warunkowe, unikając definicji „l”?
Malady
8

MATL , 7 bajtów

Z\tn2/)

Wypróbuj online!

W tym wyjaśnieniu użyjemy „12” jako próbki wejściowej. Wyjaśnienie:

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

Działa to z powodu wielu szczęśliwych zbiegów okoliczności.

  1. MATL używa 1 indeksowania
  2. <n>)n
DJMcMayhem
źródło
1
...... cóż, byłem mocno zaniepokojony!
Giuseppe
To ty musiałeś odpowiedzieć na to pytanie w MATL :-)
Luis Mendo
BTW Myślę, że możesz skrócić do Z\J2/)( J2/lub równoważnie .5joznacza, end/2gdy jest używany jako indeks)
Luis Mendo
Warto wyjaśnić zachowanie, gdy zastosuje się go do liczby z nieparzystą liczbą dzielników, ponieważ „Indeks” z wartością niecałkowitą nie jest oczywisty.
Kamil Drakari
@KamilDrakari Jak to jest?
DJMcMayhem
7

C (gcc) -lm , 35 bajtów

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

Wypróbuj online!

cleblanc
źródło
2
BTW, działa to tylko ze względu na uznanie przez GCC za sqrtfunkcję wbudowaną. Z -fno-builtin-sqrt, gcc zakłada int sqrt(int)i nie przechodzi przez double. Na x86-64 doublejest przekazywany do innego rejestru niż liczba całkowita. W wersji 32-bitowej a doublezajmie 2 miejsca na stosie, więc będziesz również przekazywał śmieci (lub wartość podnormalną z liczbą całkowitą jako dolną częścią mantysy, jeśli górne 32 bity były równe zero). To również się psuje, chyba że robisz kompilację debugowania, ponieważ opiera się na domyślnym niezoptymalizowanym genem kodu gcc do oceny wyrażeń w rejestrze wartości zwracanych.
Peter Cordes,
@PeterCordes Tak, to kod golfowy, a nie urządzenie medyczne :-)
cleblanc
Nie jestem fanem fałszywego hacka. To już nie jest nawet C, to tylko szczegół implementacji z jednym ustawieniem kompilatora, który jest domyślny. (. To naprawdę rozciąganie „musi pracować z co najmniej jednego wdrożenia” regułę) sqrt()problem jest inny: Byłem ciekaw, w jaki sposób udało się pracy, ponieważ rozmówca musi jakoś wiedzieć, aby przekształcić intsię double. Odpowiedziałem na to jako komentarz na wypadek, gdyby ktoś był ciekawy. Skutecznie gcc ma sqrt(łącznie z prototypem) wbudowaną funkcję, w przeciwnym razie nie udałoby się to z powodów, które czasami widzimy w SO asm Qs
Peter Cordes
i;f(n){for(i=0;++i<n/i||n%i;);}ma rozmiar 31B i działa gcc -Ona x86-64 (kosztuje 2 lub 3 bajty więcej dla opcji wiersza poleceń). Użycie ||zamiast |powoduje, że gcc pozostawia n/iwynik z idivEAX, rejestr wartości zwracanej ( godbolt.org/g/RJYeui ). Działa niezdefiniowane zachowanie ++ibez punktu sekwencji. (Wytworzony asm jest w zasadzie taki sam jak odpowiedź na mój kod maszynowy x86 ). Z -O0gcc zawsze wydaje się pozostawić iw EAX, ale może możemy tego użyć ...
Peter Cordes
W każdym razie, jeśli lubisz odpowiedzi na szczegóły implementacji gcc inne niż C, być może spodoba ci się ta odpowiedź x86-64 gcc, która działa, ponieważ asm generowany przez kompilator dla wyraźnie nieokreślonego zachowania: Wypróbuj online! (31 + 2 bajty)
Peter Cordes
5

05AB1E , 5 bajtów

Ñ2äнθ

Wypróbuj online! lub jako pakiet testowy

Wyjaśnienie

Ñ        # push the list of divisors
 2ä      # split it into 2 parts
   н     # take the first haft
    θ    # take the last element of that
Emigna
źródło
5

APL (Dyalog Unicode) , 16 14 12 bajtów

Cieszę się, że mogłem napisać odpowiedź w APL, ponieważ dopiero ją nauczyłem. Bardzo, bardzo dziękuję Adámowi za pomoc w grze w golfa. Sugestie dotyczące gry w golfa bardzo mile widziane. Wypróbuj online!

Aby dowiedzieć się więcej o APL, spójrz na The APL Orchard .

EDYCJA: -2 bajty do rozwiązania problemu z moim kodem. Dzięki H.PWiz za wskazanie tego problemu. -2 bajty od ponownego skrócenia wszystkiego.

⌈/{⍳⌊⍵*÷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
źródło
Dlaczego przekreślasz w odwrotnej kolejności? ... Często widzę --- 16 --- --- 14 --- 12, a nie 12 --- 14 --- --- 16 ---.
user202729,
@ user202729 Szczerze mówiąc, minęło trochę czasu i całkiem zapomniałem o kolejności przekreślenia. Naprawię to wkrótce.
Sherlock9
W rzeczywistości to nie problem, fragment tabeli liderów obsługuje oba te elementy.
user202729,
4

Łuska , 4 bajty

→←½Ḋ

Wypróbuj online!

Wyjaśnienie

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

źródło
3

x86 32-bitowy (IA32) kod maszynowy: 18 16 bajtów

dziennik zmian: n=1poprawnie obsługuj przypadek testowy, zapisz 2 bajty i wróć do EAX.

Policz do n/i <= i(tj. Kiedy dotrzemy do sqrt), a następnie użyj pierwszego dokładnego dzielnika.

Wersja 64-bitowa jest wywoływana z C przy użyciu konwencji wywoływania Systemu V x86-64, as
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

Wypróbuj online! z wywołującym asm, który wykorzystuje pierwszy bajt argumentu argv [1] bezpośrednio jako liczbę całkowitą i wykorzystuje wynik jako status zakończenia procesu.

$ 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
źródło
1
Czy jesteś pewien, że n = 1 to nie tylko 1? Jest wymieniony jako przypadek testowy i jest dzielnikiem ≤ √1 = 1.
qwr
Twoja odpowiedź powinna zadziałać dla 1. Jeśli to nie działa z twoim algorytmem, będziesz musiał go mocno kodować.
Wheat Wizard
2
@qwr: zaktualizowano krótszą wersją, która działa dla wszystkich danych wejściowych.
Peter Cordes
2

Japt -h, 8 6 bajtów

â f§U¬

Spróbuj

2 bajty zapisane dzięki Oliverowi


Wyjaśnienie

           :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
Kudłaty
źródło
Czy flagi nadal kosztują bajty?
mbomb007
@ mbomb007 Nie. Każde wystąpienie flagi jest traktowane jako nowy wpis języka.
Oliver,
Nieważne. Chyba nie widziałem jeszcze tego posta .
mbomb007
2

Bałwan , 38 bajtów

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

Wypróbuj 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
))
Klamka
źródło
2

dc , 24

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

Wypróbuj online!

Wyjaśnienie:

?                         # 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
Cyfrowa trauma
źródło
2

J, 24 19 bajtów

-5 bajtów dzięki pomysłowi Sherlocka na GCD

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

Wypróbuj online!

oryginalna odpowiedź

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

Wypróbuj online!

przeanalizowane

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

wyjaśnienie

  • 1 + i.@<.@%:daje zasięg 1 .. floor(sqrt).
  • cały czasownik (A) Btworzy hak, z powyższym zakresem przekazywanym jako prawy argument ]do A, a pierwotna liczba przekazywana jako lewy argument [. A zatem...
  • ] | [ daje pozostałą część każdego elementu w zakresie podzieloną na oryginalny argument.
  • i 0 = ] | [daje dzielniki bez reszty.
  • ] #~ ... następnie filtruje zakres, pozostawiając tylko te.
  • i {:podaje ostatni element na liście, tj. największy.
Jonasz
źródło
1

Haskell , 36 bajtów

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

Wypróbuj online!

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

yz=xxyzyz

zz

Kreator pszenicy
źródło
1

QBasic (4.5), 52 bajty

INPUT x
FOR i=1TO sqr(x)
if x/i=x\i then m=i
next
?m
Steenbergh
źródło
1

Dalej (gforth) , 53 bajty

Najkrótszym sposobem wydaje się być użycie stosu zmiennoprzecinkowego fsqrt, a najkrótszym, jaki udało mi się uzyskać bez niego, było użycie 62 bajtów /modi sprawdzenie, czy iloraz jest większy niż dzielnik.

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

Wypróbuj online!

Wyjaśnienie

  1. Oblicz pierwiastek kwadratowy
  2. Zaczynając od pierwiastka kwadratowego, zmniejszamy o 1, aż znajdziemy współczynnik oryginalnej liczby

Objaśnienie kodu

: 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
źródło
1

F #, 55 49 bajtów

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

Wypróbuj online!

Seq.findBack: Zwraca ostatni element, dla którego dana funkcja zwraca True. Funkcja w tym przypadku sprawdza, czy liczba jest czynnikiem wartości.

Ciaran_McCarthy
źródło
1

Brain-Flak , 144 bajty

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

Wypróbuj online!

Nie jestem pewien, czy ta odpowiedź jest bardzo dobra. Wydaje mi się, że może być dobry sposób na rozwiązanie tego zadania, ale po prostu nie jestem wystarczająco sprytny.

Wyjaśnienie

Próbowałem zrobić rozłożony widok odpowiedzi, ale jest tak wiele ruchomych części, że nie było to bardzo pouczające, więc oto wyjaśnienie tego, co robi kod.

Pierwszy ważny bit to

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

(x,y)xy

Następną częścią jest mnożenie, pobrane z modyfikacją z wiki . To zwielokrotnienie jest wyjątkowe, ponieważ zachowuje istniejące wartości bez ich niszczenia. To wygląda tak:

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

Pomnożymy więc wszystkie te uporządkowane pary. Dla każdego wyniku sprawdzamy, czy jest on równy wartości wejściowej. Jeśli tak, zakończymy i zwrócimy mniejszy element w parze.

Kreator pszenicy
źródło
0

Rdza, 71 70 bajtów

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

Wersja wstępnie zlepiona

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
}

Edycje

  • Oszczędź bajt z > 0ponad != 0. (Dzięki @CatWizard)
hunteke
źródło
Można !=zastąpić >?
Wheat Wizard
Dobra decyzja! Tak.
hunteke
0

Łeb , 93 bajty

{(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)))}

Możesz tego spróbować online, kopiując go do internetowego edytora Pyret !

Powyższe odnosi się do funkcji anonimowej. Po zastosowaniu do liczby całkowitej zwraca wynik zgodnie ze specyfikacją.

Tango
źródło
0

Właściwie 7 bajtów

Na podstawie mojej odpowiedzi APL tutaj . Zapraszamy do gry w golfa! Wypróbuj 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
źródło
0

Część tej odpowiedzi Mathematica .

Galaretka , 11 bajtów

½ðḞ³÷Ċ³÷µÐL

Wypróbuj online!

To (11 bajtów) również działa i nie zależy od ³:

½Ḟ÷@Ċ÷@ʋƬµṪ

Niestety ½Ḟ÷@Ċ÷@ʋÐL(10 bajtów) nie działa. I widocznie Ƭi ÐĿnie jest dokładnie taka sama (jeśli link jest dwójkowym)


n

  • i=na
  • Na każdym kroku:
    • ii
    • niainaninanian÷ni
  • in÷ni
użytkownik202729
źródło
0

Java 8, 65 54 bajtów

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

Port odpowiedzi @hunteke na Python 3 .

Wypróbuj online.


Stara 65 bajtów odpowiedź:

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

Wypróbuj online.

Wyjaśnienie:

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
źródło