Собственный делитель является делителем из числа п , которое не является п сам по себе. Например, правильными делителями 12 являются 1, 2, 3, 4 и 6.

Вам дадут целое число x , x ≥ 2, x ≤ 1000 . Ваша задача - сложить все самые высокие собственные делители целых чисел от 2 до x (включительно) (OEIS A280050 ).

Пример (с x = 6):

• Найти все целые числа от 2 до 6 (включительно): 2,3,4,5,6.

• Получить правильные делители всех из них и выбрать самые высокие из каждого числа:

  • 2 -> 1
  • 3 -> 1
  • 4 -> 1, 2
  • 5 -> 1
  • 6 -> 1, 2, 3 .

• Сумма высших правильных делителей 1 + 1 + 2 + 1 + 3 = 8.

• Окончательный результат 8.

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

Вход | Выход
------- + ---------
       |
 2 | 1
 4 | 4
 6 | 8
 8 | 13
 15 | 41
 37 | 229
 100 | 1690
 1000 | 165279

правила

• Применяются стандартные лазейки .

• Вы можете взять ввод и обеспечить вывод любым стандартным методом .

• Это код-гольф , выигрывает самая короткая действительная подача на каждом языке! Веселиться!

Оазис , 4 байта

Код:

nj+U

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

Объяснение:

Расширенная версия:

nj+00

    0   = a(0)
   0    = a(1)

a(n) =

n       # Push n
 j      # Get the largest divisor under n
  +     # Add to a(n - 1)

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

ṁȯΠtptḣ

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

объяснение

В Husk нет встроенной функции для непосредственного вычисления делителей, поэтому вместо этого я использую простую факторизацию. Самый большой правильный делитель числа - произведение его главных факторов кроме самого маленького. Я отображаю эту функцию в диапазоне от 2 до ввода и суммирую результаты.

ṁȯΠtptḣ  Define a function:
      ḣ  Range from 1 to input.
     t   Remove the first element (range from 2).
ṁ        Map over the list and take sum:
 ȯ        The composition of
    p     prime factorization,
   t      tail (remove smallest prime) and
  Π       product.

Python 2 , 50 байт

f=lambda n,k=2:n/k and(f(n,k+1),n/k+f(n-1))[n%k<1]

Это медленно и не может даже справиться с вводом 15 на TIO.

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

Однако памятка ( спасибо @ musicman523 ) может быть использована для проверки всех тестовых случаев.

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

Альтернативная версия, 52 байта

По стоимости 2 байта мы можем выбрать, вычислять f(n,k+1)или нет n/k+f(n-1).

f=lambda n,k=2:n>1and(n%k and f(n,k+1)or n/k+f(n-1))

С некоторыми хитростями, это работает для всех тестовых случаев, даже на TIO.

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

Желе , 6 байт

ÆḌ€Ṫ€S

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

Как это устроено

ÆḌ€Ṫ€S
ÆḌ€    map proper divisor (1 would become empty array)
           implicitly turns argument into 1-indexed range
   Ṫ€  map last element
     S sum

Брахилог , 10 байт

⟦bb{fkt}ᵐ+

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

JavaScript (ES6), 40 байт

f=(n,i=2)=>n<2?0:n%i?f(n,i+1):n/i+f(n-1)

<input type=number oninput=o.textContent=f(this.value)><pre id=o>

Число равно произведению его самого высокого правильного делителя и его наименьшего простого множителя.

05AB1E , 9 8 байт

-1 байт благодаря уловке главного фактора Лики Нун в его ответе Pyth

L¦vyÒ¦PO

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

объяснение

L¦vyÒ¦PO
L¦       # Range [2 .. input]
  vy     # For each...
    Ò¦    # All prime factors except the first one
      P   # Product
       O  # Sum with previous results
         # Implicit print

Альтернативное 8-байтовое решение (не работает на TIO)

L¦vyѨθO    

и ofc альтернативное 9-байтовое решение (работает на TIO)

L¦vyѨ®èO    

Сетчатка , 31 24 байта

7 байтов благодаря Мартину Эндеру.

.+
$*
M!&`(1+)(?=\1+$)
1

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

Как это устроено

Регулярное выражение /^(1+)\1+$/захватывает самый большой правильный делитель определенного числа, представленного в унарном. В коде \1+синтаксис преднамеренного преобразования.

Mathematica, 30 байт

Divisors[i][[-2]]~Sum~{i,2,#}&

Pyth , 13 9 8 байт

1 байт благодаря якоблаву.

tsm*FtPh

Тестовый пакет .

Как это устроено

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

Python 2 (PyPy) , 73 71 70 байт

n=input();r=[0]*n;d=1
while n:n-=1;r[d+d::d]=n/d*[d];d+=1
print sum(r)

Не самый короткий ответ Python, но он просто проходит через контрольные примеры. TIO обрабатывает до 30 000 000 входов без всяких потов; Мой настольный компьютер обрабатывает 300 000 000 в минуту.

При стоимости 2 байта условие n>dможет быть использовано для ускорения ~ 10%.

Спасибо @xnor за r=[0]*nидею, которая сэкономила 3 ​​байта!

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

Haskell, 48 46 43 байта

f 2=1
f n=until((<1).mod n)pred(n-1)+f(n-1)

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

Редактировать: @rogaos сохранил два байта. Благодарность!

Редактировать II: ... и @xnor еще 3 байта.

Japt , 8 + 2 = 10 8 6 байт

òâ1 xo

Проверь это

• 1 байт сохранен благодаря ETHproductions.

объяснение

    :Implicit input of integer U.
ò   :Generate an array of integers from 1 to U, inclusive
â   :Get the divisors of each number,
1   :  excluding itself.
x   :Sum the main array
o   :by popping the last element from each sub-array.
    :Implicit output of result

MATL, 12 байт

q:Q"@Z\l_)vs

Попробуйте это на MATL Online

объяснение

        % Implicitly grab input (N)
q       % Subtract one
:       % Create an array [1...(N-1)]
Q       % Add one to create [2...N]
"       % For each element
  @Z\   % Compute the divisors of this element (including itself)
  l_)   % Grab the next to last element (the largest that isn't itself)
  v     % Vertically concatenate the entire stack so far
  s     % Sum the result

PHP , 56 байт

for($i=1;$v||$argn>=$v=++$i;)$i%--$v?:$v=!$s+=$v;echo$s;

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

Пролог (SWI) , 72 байта

f(A,B):-A=2,B=1;C is A-1,f(C,D),between(2,A,E),divmod(A,E,S,0),B is D+S.

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

Cubix , 27 39 байт

?%\(W!:.U0IU(;u;p+qu.@Op\;;

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

Cubified

      ? % \
      ( W !
      : . U
0 I U ( ; u ; p + q u .
@ O p \ ; ; . . . . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

Смотреть это работает

• 0IUУстановите стек с аккумулятором и начальным целым числом. Разворот во внешний цикл
• :(? дублировать текущую вершину стека, декремент и тест
• \pO@ если ноль зацикливается вокруг куба до зеркала, возьмите дно стека, выведите и остановите
• %\! если положительный, мод, отобрать и проверить.
  • u;.W если правда, развернись, убери результат мода и перестроись обратно во внутренний цикл
  • U;p+qu;;\(если фальси, разворот, удалите результат мода, приведите аккумулятор к вершине, добавьте текущий целочисленный (верхний) делитель толчка к низу и разворот. Очистите стек, чтобы получить только аккумулятор и текущее целое число, уменьшить число и снова войти во внешний цикл.

C # (.NET Core) , 74 72 байта

n=>{int r=0,j;for(;n>1;n--)for(j=n;--j>0;)if(n%j<1){r+=j;j=0;}return r;}

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

• 2 байта побрились благодаря Кевину Круйссену.

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

u2x⌠÷R1@E⌡MΣ

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

Python 3 , 78 75 73 71 байт

Даже близко к ответу Python про Лаки Монахини в подсчете байтов.

f=lambda z:sum(max(i for i in range(1,y)if 1>y%i)for y in range(2,z+1))

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

Python 3 , 69 63 59 байт

4 байта благодаря Денису.

f=lambda n:n-1and max(j for j in range(1,n)if n%j<1)+f(n-1)

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

Я установил предел рекурсии на 2000, чтобы он работал на 1000.

Древесный уголь , 37 байт

Ａ⁰βＦ…·²Ｎ«Ａ⟦⟧δＦ⮌…¹ι«¿¬﹪ικ⊞δκ»Ａ⁺β⌈δβ»Ｉβ

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

Ссылка на подробную версию. Мне потребовался почти весь день, чтобы понять, как я могу решить вопрос, не связанный с ASCII-искусством, в Charcoal, но, наконец, я его получил и очень горжусь собой. :-D

Да, я уверен, что это может быть много в гольфе. Я только что перевел свой ответ на C # и уверен, что в Charcoal все можно сделать по-другому. По крайней мере, это решает 1000дело за пару секунд ...

Пари / ГП , 36 30 байт

n->sum(i=2,n,i/divisors(i)[2])

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

Python 2 (PyPy) , 145 байт

Поскольку превращение соревнований код-гольф в соревнованиях быстро кодовыми весело, здесь есть O ( п алгоритм ), который в TIO решает n = 5 000 000 000 за 30 секунд. ( Сито Денниса - O ( n log n ).)

import sympy
n=input()
def g(i,p,k,s):
 while p*max(p,k)<=n:l=k*p;i+=1;p=sympy.sieve[i];s-=g(i,p,l,n/l*(n/l*k+k-2)/2)
 return s
print~g(1,2,1,-n)

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

Как это устроено

Подсчитаем размер набора

S = {( а , b ) | 2 ≤ a ≤ n , 2 ≤ b ≤ наибольший собственный делитель ( a )},

переписав его как объединение по всем простым числам p ≤ √n,

S _p = {( p ⋅ d , b ) | 2 ≤ d ≤ n / p , 2 ≤ b ≤ d },

и используя принцип включения-исключения :

| S | = ∑ (−1) ^{m - 1} | S _{p 1} ∩ ⋯ ∩ S _{p m} | свыше m ≥ 1 и простых чисел p ₁ <⋯ < p _m ≤ √n,

где

S _{p 1} ∩ ⋯ ∩ S _{p m} = {(p₁⋯p _m ⋅e,b) | 1 ≤e≤n/ (p₁⋯p _m ), 2 ≤b≤p₁⋯p _{m - 1}e},
| S _{p 1} ∩ ⋯ ∩S _{p m} | = ⌊n/ (p₁⋯p _m ) ⌋⋅ (p₁⋯ p_{m - 1}⋯ p _m ) ⌋ + 1) - 2) / 2. ⋅ (⌊ n / (р ₁

Сумма имеет C ⋅ n ненулевых членов, где C сходится к некоторой константе, которая, вероятно, 6 probably (1 - ln 2) / π ² ≈ 0.186544. Окончательный результат тогда | S | + n - 1.

NewStack , 5 байт

К счастью, на самом деле есть встроенный.

Nᵢ;qΣ

Разбивка:

Nᵢ       Add the first (user's input) natural numbers to the stack.
  ;      Perform the highest factor operator on whole stack.
   q     Pop bottom of stack.
    Σ    Sum stack.

На реальном английском языке:

Давайте запустим пример для ввода 8.

Nᵢ: Составьте список натуральных чисел от 1 до 8: 1, 2, 3, 4, 5, 6, 7, 8

;: Вычислить самые большие факторы: 1, 1, 1, 2, 1, 3, 1, 4

q, Удалить первый элемент:1, 1, 2, 1, 3, 1, 4

ΣИ возьми сумму: 1+1+2+1+3+1+4=13

Java 8, 78 74 72 байта

n->{int r=0,j;for(;n>1;n--)for(j=n;j-->1;)if(n%j<1){r+=j;j=0;}return r;}

Порт @CarlosAlejo на C #.

Попробуй это здесь.

Старый ответ (78 байт):

n->{int r=0,i=1,j,k;for(;++i<=n;r+=k)for(j=1,k=1;++j<i;k=i%j<1?j:k);return r;}

Попробуй это здесь.

Объяснение (старого ответа):

n->{                    // Method with integer parameter and integer return-type
  int r=0,              //  Result-integers
      i=1,j,k;          //  Some temp integers
  for(;++i<=n;          //  Loop (1) from 2 to `n` (inclusive)
      r+=k)             //    And add `k` to the result after every iteration
    for(j=1,k=1;++j<i;  //   Inner loop (2) from `2` to `i` (exclusive)
      k=i%j<1?j:k       //    If `i` is dividable by `j`, replace `k` with `j`
    );                  //   End of inner loop (2)
                        //  End of loop (2) (implicit / single-line body)
  return r;             //  Return result-integer
}                       // End of method

Lua , 74 байта

c=0 for i=2,...do for j=1,i-1 do t=i%j<1 and j or t end c=c+t end print(c)

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

J , 18 байт

[:+/1}.&.q:@+}.@i.

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

С накоплением , 31 байт

[2\|>[divisors:pop\MAX]map sum]

Попробуйте онлайн! (Все тестовые случаи, кроме 1000, что превышает 60 секунд онлайн-лимита.)

объяснение

[2\|>[divisors:pop\MAX]map sum]
 2\|>                               range from 2 to the input inclusive
     [                ]map          map this function over the range
      divisors                      get the divisors of the number (including the number)
              :pop\                 pop a number off the array and swap it with the array
                   MAX              gets the maximum value from the array
                           sum      sum's all the max's

C (gcc) , 53 байта

x;s;f(n){for(s=0;n>1;--n){for(x=n;n%--x;);s+=x;}n=s;}

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

Комфортно быстро проходит все тестовые случаи.