Вдохновленный цифровыми корнями, основной факторный корень числа - это число, которое появляется, когда вы берете основные множители числа, складываете их вместе и повторяете процесс для полученного числа, продолжая, пока не получите простое число ( который имеет себя в качестве своего единственного первичного фактора и, таким образом, является его собственным первичным факторным корнем). Первичный факторный корень из 4 равен 4, так как 2 * 2 = 2 + 2, и это единственный непростой простой факторный корень из целого числа, большего 1 (что является еще одним частным случаем, поскольку у него нет простых факторов). Последовательность OEIS, образованная простыми факторными корнями, является A029908 .

Например, основной факторный корень 24:

24=2*2*2*3

2+2+2+3=9=3*3

3+3=6=2*3

2+3=5, and the only prime factor of 5 is 5.  Therefore, the prime factoral root of 24 is 5.  

Твое задание:

Напишите программу или функцию, которая находит основной факторный корень входного целого числа.

Входные данные:

Целое число, введенное любым разумным способом, между 2 и наибольшим целым числом, которое поддерживает ваш язык (включительно). В частности, выбор языка с необоснованно низким максимальным целочисленным размером недопустим (а также нарушает эту стандартную лазейку )

Выход:

Целое число, основной факторный корень входных данных.

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

4   -> 4
24  -> 5
11  -> 11
250 -> 17

Подсчет очков:

Это код-гольф , выигрывает самая низкая оценка в байтах!

05AB1E , 3 байта

FÒO

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

Пояснения:

FÒO   
F    Loops <input> times + 1
 Ò   List of prime factors w/ duplicates
  O  Total sum of the list
     -- implicit output

Haskell , 61 байт

import Data.Numbers.Primes
until=<<((==)=<<)$sum.primeFactors

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

объяснение

until=<<((==)=<<)берет функцию fи применяет ее для ввода, xпока не будет достигнута фиксированная точка, то есть f xравна x. primeFactorsвозвращает список простых факторов числа, возвращает sumсумму списка чисел.

Но подожди, почему until=<<((==)=<<) работа и выглядит так странно?

Если мы предположим f=sum.primeFactors, более естественное определение будет until(\x->f x==x)f, потому что untilпринимает предикат (функция, которая возвращает логическое значение), функцию, которая имеет тот же тип ввода и возврата (например Int -> Int) и значение этого типа, а затем применяет функцию к значение до тех пор, пока предикат не будет выполнен.

until(\x->f x==x)fтакая же , как until(\x->(==)(f x)x)fи как она считает , что g (h x) xэто так же , как (g=<<h)xмы получаем until(\x->((==)=<<f)x)f. После Eta преобразования это становится until((==)=<<f)f. Но если мы теперь будем рассматривать (==)=<<как функцию, к которой применяется f, мы можем увидеть, что until(((==)=<<)f)fона снова имеет форму g (h x) x, с g=until, h=((==)=<<)и x=f, таким образом, она может быть переписана (until=<<((==)=<<))f. Использование $оператора , чтобы избавиться от внешних скобок и подставляя fс sum.primeFactorsвыходами решения сверху.

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

ω(Σp

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

Объяснение:

ω(   -- apply the following function until the result no longer changes (fixpoint)
  Σ  -- sum
   p -- the list of primefactors

Pyth , 3 байта

usP

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

Объяснение:

usPGQ The trailing GQ is implicit
  PG  Get prime factors
 s    Sum
u   Q Repeat until returned value no longer unique starting with the input

Python 2 , 84 байта

f=lambda n,d=2:n>1and(n%d and f(n,d+1)or d+f(n/d))
i=input()
exec'i=f(i);'*i
print i

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

Java 8, 175 144 142 141 байт

n->{for(int i,t=n,x;;n=t){for(i=2;i<t;t=t%i++<1?0:t);if(t>1|n<5)return n;for(t=0,i=1;i++<n;)for(;n%i<1;n/=i,t+=x)for(x=i;x>9;x/=10)t+=x%10;}}

-1 байт благодаря @Nevay .

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

Объяснение:

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

n->{                // Method with integer as both parameter and return-type
  for(int i,        //  Index-integer `i`
          t=n,      //  Temp integer `t`, starting at the input `n`
          x;        //  Temp integer `x`
      ;             //  Loop (1) indefinitely
      n=t){         //    After every iteration, replace `n` with the value `t`
    for(i=2;        //   Reset `i` to 2
        i<t;        //   Inner loop (2) from 2 to `t` (exclusive)
        t=t%i++<1?  //    If `t` is divisible by `i`:
           0        //     Set `t` to 0
          :         //    Else:
           t        //     Leave `t` the same
    );              //   End of inner loop (2)
    if(t>1          //   If `t` is not 0 (it means it's a prime),
       |n<5)        //   or if `n` is below 5 (for edge-cases `4` and 'prime' `1`)
      return n;     //    Return `n` as result
    for(t=0,        //   Reset `t` to 0
        i=1;        //   Reset `i` to 1
        i++<n;)     //   Inner loop (3) from 2 to `n` (inclusive)
      for(;n%i<1;   //    Inner loop (4) as long as `n` is divisible by `i`
          n/=i,     //      After every iteration: Divide `n` by `i`,
          t+=x)     //      and increase `t` by `x`
        for(x=i;    //     Reset `x` to `i`
            x>9;    //     Inner loop (5) as long as `x` contains more than 1 digit
            x/=10)  //       After every iteration, remove the trailing digit
          t+=n%10;  //      Increase `t` with the trailing digit of `n`
                    //     End of inner loop (5) (implicit / single-line body)
                    //    End of inner loop (4) (implicit / single-line body)
                    //   End of inner loop (3) (implicit / single-line body)
  }                 //  End of loop (1)
}                   // End of method

Желе , 5 байт

ÆfS$¡

Пояснения:

Æf    list of prime factors
  S   sum
   $¡ repeat n times

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

Сетчатка , 30 байт

{+`(\1|\b11+?\B)+$
$1;$#1$*
;

Ввод и вывод в одинарный .

Попробуйте онлайн! (Выполняет десятичное / унарное преобразование для удобства.)

объяснение

{+`(\1|\b11+?\B)+$
$1;$#1$*

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

Этот этап сам вычисляет основную факторизацию входных данных. Это +похоже на, {но зацикливает только этот этап, пока не прекратит изменять строку. Регулярное выражение пытается сопоставить последний прогон 1s, многократно сопоставляя одну и ту же подстроку (т. Е. Фактор). То, как это сделано, немного запутано из-за прямой ссылки \1. На первой итерации группа 1еще ничего не захватила, поэтому \1безоговорочно завершается. Вместо этого мы должны сопоставить, \b11+?\Bкакая наименьшая возможная подстрока начинается в начале цикла, содержит не менее двух 1секунд и не охватывает весь цикл. Последующие итерации не смогут снова использовать эту альтернативу из-за \b. Таким образом, на всех дальнейших итерациях мы сопоставляем\1то есть одна и та же подстрока снова и снова. Этот процесс должен точно достигнуть конца строки ( $), чтобы убедиться, что мы зафиксировали фактический делитель. Преимущество использования этого несколько хитрого подхода состоит в том, что группа 1будет использоваться ровно n / d раз, то есть то, что остается после деления делителя d .

Мы заменяем это совпадение на d ( $1), разделение ;и n / d ( $#1$*который вставляет $#1копии 1, где $#1число захватов, сделанных группой 1).

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

;

Все, что нам нужно сделать, чтобы сложить простые числа, это удалить все разделители.

Ом v2 , 4 байта

·ΘoΣ

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

Объяснение:

·Θ    evaluate the block until the result returned has already been seen
   Σ  sum
  o   the full prime factorization

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

⌠w♂πΣ⌡Y

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

Объяснение:

⌠w♂πΣ⌡Y
⌠    ⌡Y  do this until output stops changing (fixed-point combinator)
 w         factor into [prime, exponent] pairs
  ♂π       product of each pair
    Σ      sum of products

R + Pracma , 53 байта

function(n){for(i in 1:n)n=sum(pracma::factors(n))
n}

Попробуйте онлайн! (Г-скрипка)

R не имеет простые множители встроенные, но многочисленные пакеты ( pracma, numbersи т.д.) делать, поэтому я выбрал удобно короткий.

Желе , 6 байт

В этом ответе используется один из многих основных факторов факторизации Jelly, и быстрый для repeat until the results are no longer unique.

ÆfSµÐL

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

MATL , 6 байтов

Использует идею Скоттинет зацикливания больше раз, чем необходимо. Спасибо также Шегги за указание на ошибку, которая теперь исправлена.

t:"Yfs

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

объяснение

t       % Take input (implicit). Duplicate
:"      % Do the following that many times
  Yf    %   Array of prime factors
  s     %   Sum of array
        % End (implicit). Display (implicit)

PowerShell , 124 байта

function f($a){for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}
for($x=$args[0];$l-ne$x){$l=$x;$x=(f($x))-join'+'|iex}$x

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

PowerShell не имеет встроенных основных факторов факторизации, поэтому для выполнения расчетов факторизации используется код из моего ответа на Prime Factors Buddies (верхняя строка).

Вторая строка - это мясо этой программы. Мы принимаем входные данные $argsв $x, затем forзацикливаемся до тех пор, пока $lне -nполучим eквалификацию $x. (Первая итерация,$l является$null и $xявляется целым числом, так что мы будем цикл по крайней мере , один раз).

Внутри цикла мы устанавливаем нашу команду, $l = $xчтобы определить, достигли мы конца цикла или нет. Затем мы получаем факторы $xс f($x), -joinте вместе с ними +и |iexих (сокращение Invoke-Expressionи аналог eval). Это хранится обратно в $x. Таким образом, мы достигли «конца», когда сложенная вместе основная факторизация возвращается к себе. Затем мы просто помещаем $xв конвейер и вывод неявный.

Mathematica, 35 байт

#//.x_:>Tr[1##&@@@FactorInteger@x]&

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

(Mathics не поддерживает Tr. Я должен реализовать это вручную)

Рубин , 63 байта

->n{n.times{n=n.prime_division.map{|x|x.reduce:*}.sum};n}

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

Использует -rprimeфлаг для +6 байтов, чтобы использовать Prime # prime_division .

prime_divisionвозвращает пары [prime, exponent](например, для 24 у нас есть факторы, которые [2, 2, 2, 3]он дает [[2, 3], [3, 1]]), поэтому на каждом шаге мы просто умножаем члены этих пар вместе и суммируем результаты.

Javascript (ES6), 63 байта

f=n=>(q=(p=(m,x)=>m<x?0:m%x?p(m,x+1):x+p(m/x,x))(n,2))^n?f(q):q

<input id=i type=number min=0 value=0 oninput="o.innerText=f(i.value)">
<p id=o></p>

Ungolfed:

f=n=>(                  // Recursive function `f`
    p=(m,x=2)=>(        //   Recursive function `p`, used to sum prime factors
        m<x?            //     If m (the number to be factored) is less than x (the current
            0           //     iteration), return 0
        :m%x?           //     Else if m doesn't divide x
            p(m,x+1)    //     run the next iteration
        :               //     Else (if m divides x)
            x+p(m/x,x)  //     Divide m by x and repeat the current iteration
    ),
    q=p(n),             //   Set q to the sum of the prime factors of n
    q^n?                //   If q != n then
        f(q)            //     repeat f with q
    :                   //   else
        q               //     return q
)

Java 8, 101 байт

n->{for(int i=n;i-->0;n=f(n,2));return n;}int f(int n,int d){return n>1?n%d>0?f(n,d+1):d+f(n/d,2):0;}

Порт @ovs удивительный ответ Python 2 .

Объяснение:

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

n->{                  // Method with integer as both parameter and return-type
  for(int i=n;i-->0;  //  Loop the input amount of times
    n=f(n,2)          //   And change `n` that many times with a separate method call
  );                  //  End of loop
  return n;           //  Then return the integer `n` as result
}                     // End of method

int f(int n,int d){   // Separated method with 2 integer parameters and integer return-type
                      // (`d` is 2 when we initially call this recursive-method)
  return n>1?         //  If input `n` is larger than 1:
    n%d>0?            //   And it's not divisible by `d`:
     f(n,d+1)         //    Do a recursive-call with `n, d+1`
    :                 //   Else:
     d                //    Sum `d` with
      +f(n/d,2)       //    a recursive call with `n/d, 2`
   :                  //  Else:
    0;                //   Simply return 0
}                     // End of separated method