Напишите код, который при получении положительного числа качестве ввода выводит наибольший положительный делитель x, меньший или равный квадратному корню из x .$x$$x$$x$

Другими словами, найдите наибольшее такое, что$n > 0$

$\exists m\geq n:m\cdot n=x$

^{(Существует большее или равное n, такое что m умноженное на n равно x )$m$$n$$m$$n$$x$}

Например, если на входе было делителей, это 1 , 2 , 3 , 4 , 6 и 12 . 1 , 2 и 3 все умножаются на большие числа, чтобы получить 12 , но 3 является наибольшим, поэтому мы возвращаем 3 .$12$$1$$2$$3$$4$$6$$12$$1$$2$$3$$12$$3$$3$

Это код-гольф, поэтому ответы будут оцениваться в байтах, причем меньшее количество байтов будет считаться лучшим результатом.

Тестовые случаи

(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

Python3 , 49 47 байт

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

объяснение

• l=x**.5//1→ Назначить lнаибольшее целое число меньше, чем квадратный корень изx
• while x%l:l-=1→ Пока lне делится поровну x, уменьшать l.

Правки

• Упомяните Python3, а не Python2
• Используйте, ...//1чтобы сохранить два байта. (Десятичные числа в порядке! Спасибо @Rod)

MATL , 7 байт

Z\tn2/)

Попробуйте онлайн!

Для этого объяснения мы будем использовать «12» в качестве примера ввода. Объяснение:

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

Это работает из-за большого количества счастливых совпадений.

1. MATL использует 1 индексирование
2. Если мы будем индексировать нецелым числом (это произойдет для любого идеального квадратного ввода), то мы <n>)будем индексировать $\lceil n \rceil$

C (gcc) -lm , 35 байт

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

Попробуйте онлайн!

05AB1E , 5 байтов

Ñ2äнθ

Попробуйте онлайн! или как тестовый набор

объяснение

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

APL (Dyalog Unicode) , 16 14 12 байт

Я рад, что смог написать какой-то ответ в APL, так как я только что узнал об этом. Большое, большое спасибо Адаму за помощь в игре в гольф. Предложения по гольфу очень приветствуются. Попробуйте онлайн!

Чтобы узнать больше об APL, взгляните на APL Orchard .

РЕДАКТИРОВАТЬ: -2 байта для устранения проблемы с моим кодом. Спасибо H.PWiz за указание на эту проблему. -2 байта от повторного сокращения.

⌈/{⍳⌊⍵*÷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.

Шелуха , 4 байта

→←½Ḋ

Попробуйте онлайн!

объяснение

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

R , 45 33 байта

function(x,y=1:x^.5)max(y[!x%%y])

Попробуйте онлайн!

Оригинал:

function(x,y=x/1:x^.5)max(which(y==floor(y)))

Попробуйте онлайн!

32-битный (IA32) машинный код x86: 18 16 байт

changelog: n=1правильно обработать контрольный пример, сохранить 2 байта и вернуться в EAX.

Считайте до n/i <= i(т. Е. Когда мы достигнем sqrt), и используйте первый точный делитель после этого.

64-битная версия этого вызывается из C с соглашением о вызовах System 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

Попробуйте онлайн! с вызывающей программой asm, которая использует первый байт argv [1] как целое число напрямую и использует результат как состояние завершения процесса.

$ 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
   ...

Japt -h, 8 6 байт

â f§U¬

Попытайся

2 байта спасены благодаря Оливеру

объяснение

           :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

Желе , 5 байт

ọⱮ½TṪ

Попробуйте онлайн!

JavaScript ES7, 33 31 байт

n=>(g=x=>n%x?g(x-1):x)(n**.5|0)

Попробуйте онлайн

Снеговик , 38 байт

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

Попробуйте онлайн!

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

DC , 24

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

Попробуйте онлайн!

Объяснение:

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

J, 24 19 байт

-5 байт благодаря идее Шерлока GCD

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

Попробуйте онлайн!

оригинальный ответ

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

Попробуйте онлайн!

разобранный

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

объяснение

• 1 + i.@<.@%:дает диапазон 1 .. floor(sqrt).
• весь глагол (A) Bобразует зацепку, с указанным выше диапазоном, переданным как правый аргумент ]A, и исходным числом, переданным как его левый аргумент [. Таким образом , ...
• ] | [ дает остаток каждого элемента в диапазоне, разделенном на исходный аргумент.
• и 0 = ] | [дает делители без остатка.
• ] #~ ... затем фильтрует диапазон, оставляя только те.
• и {:дает последний элемент в списке, т.е. самый большой.

Желе , 5 байт

½ḍƇµṪ

Попробуйте онлайн!

Haskell , 36 байт

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

Попробуйте онлайн!

$y$[1..]$z$[1..y]$(y,z)$$y \geq z$

$y\cdot z=x$$x$$y$$z$$y$$z$

$z$$z$

QBasic (4.5), 52 байта

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

Forth (gforth) , 53 байта

Самый короткий путь, кажется, использует стек с плавающей запятой, и fsqrtсамый короткий путь, который я мог получить без него, был 62 байтами, используя /modи проверяя, было ли частное больше делителя.

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

Попробуйте онлайн!

объяснение

1. Рассчитать квадратный корень
2. Начиная с квадратного корня, уменьшайте на 1, пока мы не найдем множитель исходного числа

Код Объяснение

: 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

F #, 55 49 байтов

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

Попробуйте онлайн!

Seq.findBackВозвращает последний элемент, для которого возвращается данная функция True. Функция в этом случае проверяет, является ли число фактором фактора.

Brain-Flak , 144 байта

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

Попробуйте онлайн!

Я не совсем уверен, что этот ответ очень хороший. Я чувствую, что может быть хороший способ решить эту задачу, но я не достаточно умен.

объяснение

Я попытался сделать ответ в разобранном виде, но движущихся частей было так много, что это было не очень поучительно, поэтому вот объяснение того, что делает код.

Первый важный момент это

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

$(x,y)$$x \geq y$

Следующая часть - умножение, взятое с модификацией из вики . Это умножение является особенным, поскольку оно сохраняет существующие значения, не разрушая их. Это идет как:

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

Итак, мы умножаем все эти упорядоченные пары. Для каждого результата мы проверяем, равен ли он входу. Если это так, мы прекращаем и возвращаем меньший элемент в паре.

Python 2 , 41 байт

n=k=input()
while(k*k>n)+n%k:k-=1
print k

Попробуйте онлайн!

Желе , 6 байт

ÆDŒHḢṪ

Попробуйте онлайн!

Perl 5 -p , 26 байт

$\=0|sqrt;$\--while$_%$\}{

Попробуйте онлайн!

Ржавчина, 71 70 байт

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

Предварительно улучшенная версия

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
}

Правки

• Сохранить байт с > 0более чем != 0. (Спасибо @CatWizard)

Japt , 8 байт

â w æ§Uq

Попробуйте онлайн!

Треугольность , 49 байтов

....)....
...@_)...
..IEdF)..
.2)1/)IE.
^>{m.....

Попробуйте онлайн!

Pyret , 93 байта

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

Вы можете попробовать это онлайн, скопировав его в онлайн-редактор Pyret !

Выше оценивается анонимная функция. Когда он применяется к целому числу, он возвращает результат в соответствии со спецификацией.

На самом деле 7 байтов

На основании моего ответа APL здесь . Предложения по игре в гольф приветствуются! Попробуйте онлайн!

;√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.

Порт этого Mathematica ответа .

Желе , 11 байт

½ðḞ³÷Ċ³÷µÐL

Попробуйте онлайн!

Это (11 байт) также работает и не зависит от ³:

½Ḟ÷@Ċ÷@ʋƬµṪ

К сожалению ½Ḟ÷@Ċ÷@ʋÐL(10 байт) не работает. И видимо ƬиÐĿ не совсем то же самое (когда ссылка диадическая)

$n$

• $i = \sqrt n$$a$ .
• На каждом этапе:
  • $i$$\lfloor i\rfloor$ (потому что результат должен быть целым числом)
  • $n\over i$$a \le i \Rightarrow \frac n a \ge \frac n i \Rightarrow \frac n a \ge \lceil \frac n i \rceil \Rightarrow a \le n \div \lceil \frac n i \rceil$
• $i$$n \div \lceil \frac n {\lfloor i\rfloor} \rceil$

Java 8, 65 54 байта

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

Порт @hunteke 's Python 3 ответа .

Попробуйте онлайн.

Старый 65-байтовый ответ:

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

Попробуйте онлайн.

Объяснение:

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`