Некоторые числа, например, 64можно выразить как целое число несколькими способами:

64 ^ 1
 8 ^ 2
 4 ^ 3
 2 ^ 6

Выведите отсортированный массив всех возможных таких степеней (здесь [1,2,3,6]) в минимально возможном количестве байтов.

вход

Целое положительное число больше 1 и меньше 10000.

Выход

Массив степеней целых чисел p(включая 1), для которых вход может быть выражен как a^pцелое число a. Выходы могут иметь десятичные дроби, если они в порядке.

Любые проблемы с плавающей точкой должны быть обработаны программой.

Примеры

Input: 3
Output: [1]

Input: 9
Output: [1, 2]

Input: 81
Output: [1, 2, 4]

Input: 729
Output: [1, 2, 3, 6]

Табло

Чтобы ваш счет отображался на доске, он должен быть в следующем формате:

# Language, Bytes

Зачеркивание не должно вызывать проблем.

function getURL(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:getURL(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),useData(answers)}})}function getOwnerName(e){return e.owner.display_name}function useData(e){var s=[];e.forEach(function(e){var a=e.body.replace(/<s>.*<\/s>/,"").replace(/<strike>.*<\/strike>/,"");console.log(a),VALID_HEAD.test(a)&&s.push({user:getOwnerName(e),language:a.match(VALID_HEAD)[1],score:+a.match(VALID_HEAD)[2],link:e.share_link})}),s.sort(function(e,s){var a=e.score,r=s.score;return a-r}),s.forEach(function(e,s){var a=$("#score-template").html();a=a.replace("{{RANK}}",s+1+"").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SCORE}}",e.score),a=$(a),$("#scores").append(a)})}var QUESTION_ID=58047,ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],answer_ids,answers_hash,answer_page=1;getAnswers();var VALID_HEAD=/<h\d>([^\n,]*)[, ]*(\d+).*<\/h\d>/;

body{text-align:left!important}table thead{font-weight:700}table td{padding:10px 0 0 30px}#scores-cont{padding:10px;width:600px}#scores tr td:first-of-type{padding-left:0}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="scores-cont"><h2>Scores</h2><table class="score-table"><thead> <tr><td></td><td>User</td><td>Language</td><td>Score</td></tr></thead> <tbody id="scores"></tbody></table></div><table style="display: none"> <tbody id="score-template"><tr><td>{{RANK}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SCORE}}</td></tr></tbody></table>

Pyth, 10 байт

f}Q^RTSQSQ

демонстрация

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

Хаскелл, 38

f n=[b|b<-[1..n],n`elem`map(^b)[1..n]]

Довольно просто. Понимание списка находит значения, bдля которых ввод nпоявляется среди [1^b, 2^b, ..., n^b]. Достаточно проверить bв диапазоне [1..n].

Python 2, 53

lambda n:[i/n for i in range(n*n)if(i%n+1)**(i/n)==n]

Грубая сила все комбинации базисов в показателях в [0, n-1] и базисов в [1, n].

Python 3, 56 байт

lambda n:[i for i in range(1,n)if round(n**(1/i))**i==n]

Это действительно неуклюже. Проверяет, iдает ли каждый потенциальный корень число целое, округляя его, получая его мощность iи проверяя, соответствует ли оно оригиналу.

Непосредственно проверить, что корень является целым числом, сложно, потому что числа с плавающей запятой дают такие вещи, как 64**(1/3) == 3.9999999999999996. Округляя его до целого числа, давайте проверим, вернется ли возврат к исходному значению. Спасибо ypercube за предложение об экономии 1 байта.

У feersum есть более короткое и умное решение . Вы все должны действительно поддержать это.

Pyth, 11 10 12 байт

fsmqQ^dTSQSQ

Проверяет все возможные комбинации полномочий. Очень медленно.

CJam, 23 байта

rimF{1=:E){E\d%!},}%:&p

Это работает, беря простую факторизацию n и вычисляя пересечение делителей всех показателей.

Это немного дольше, чем мое другое решение , но я ожидаю, что оно будет работать (и закончится мгновенно) для всех целых чисел от 2 до 2 ⁶³ - 1 .

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

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

ri                       Read an integer from STDIN.
  mF                     Push its prime factorization.
    {             }%     For each [prime exponent]:
     1=:E                  Retrieve the exponent and save it in E.
         ){     },         Filter; for each I in [0 ... E]:
           E\d%              Compute E % Double(I).
                             (Casting to Double is required to divide by 0.)
               !             Push the logical NOT of the modulus.
                           Keep I if the result is truhty, i.e., if I divides E.
                    :&   Intersect all resulting arrays of integers.
                      p  Print the resulting array.

APL, 17 байт

(X=⌊X←N*÷⍳N)/⍳N←⎕

Моя первая программа APL; Гольф предложения приветствуются.

              N←⎕  ⍝ Store input into N
             ⍳     ⍝ The list [1 2 ... N]
            /      ⍝ Select the elements A for which
      N*÷⍳N)       ⍝ N^(1/A)
(X=⌊X←             ⍝ equals its floor (that is, is an integer)

JavaScript (ES5), 73 байта, 81 байт, 79 байтов, 75 байтов

for(n=+prompt(),p=Math.pow,i=0;i++<n;)p(.5+p(n,1/i)|0,i)==n&&console.log(i)

Проверяет, равна ли ближайшая целочисленная степень возможного корня n. ~~(.5+...)эквивалентно Math.round(...)для выражений в диапазоне целых чисел (от 0 до 2 ^ 31 - 1).

Изменить: Использовать ленивую &&логику вместо того, ifчтобы брить 2 байта и добавил подсказку для ввода, так как вопрос добавил пояснение. Ранее предполагалось, что вход был сохранен в n.

Редактировать 2: Изменено, ~~(.5+...)чтобы .5+...|0сохранить два байта, избегая группировки.

Редактировать 3: Удалено, varчтобы сохранить 4 байта. В нестрогом режиме это приемлемо.

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

≥^↙.?≥ℕ≜

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

Принимает входные данные через свою входную переменную и генерирует каждую мощность через свою выходную переменную в порядке возрастания, как требуется, в отличие от старого решения, ≥ℕ≜^↙.?∧которое, как оказалось, имеет точно такую ​​же длину.

≥           Some number which is less than or equal to
            the input,
 ^          when raised to the power of
  ↙.        the output,
    ?       is the input.
       ≜    Label
            the output
      ℕ     as a whole number
     ≥      which is less than or equal to
    ?       the input.

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

ḋḅlᵛfэто гораздо более короткое (не генераторное) решение для всех заданных тестовых случаев, но оно терпит неудачу, если вход не является степенью произведения различных простых чисел. (Если подумать, поскольку все тестовые случаи являются степенями простых чисел, они ḋlfтоже работают ...) Лучшее, что я придумал, чтобы спасти идею, ḋḅlᵐḋˢ⊇ᵛ×f- это 10 байтов.

Желе , 6 байт

ÆEg/ÆD

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

    ÆD    The list of divisors of
ÆE        the exponents in the prime factorization of the input
   /      reduced by
  g       greatest common divisor.

05AB1E , 3 байта

Ó¿Ñ

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

Порт желе несвязанного ответа .

Ó       # exponents in the prime factorization
 ¿      # gcd
  Ñ     # divisors

JavaScript ES7, 66 байт

Принимает преимущество экспериментальных постижений массива. Работает только на Firefox.

n=>[for(i of Array(n).keys(m=Math.pow))if(m(0|.5+m(n,1/i),i)==n)i]

Возможен гольф. Я, вероятно, постараюсь сжать выражения немного короче и, надеюсь, найду альтернативу длинному Array(n).keys()синтаксису.

Может быть короче, но JavaScript имеет ужасную точность с плавающей точкой.

CJam, 20 байт

ri_,1df+\1$fmL9fmO&p

Для ввода n это вычисляет log _b n для всех b, меньших или равных n, и сохраняет результаты, которые являются целыми числами.

Это должно работать для всех целых чисел от 2 и 9,999 . Время выполнения примерно O (n) .

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

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

ri                   e# Read an integer N from STDIN.
  _,                 e# Copy N and transform it into [0 ... N-1].
    1df+             e# Add 1.0 to each, resulting in [1.0 ... Nd].
        \1$          e# Swap the array with N and copy the array.
           fmL       e# Mapped log base N: N [1.0 ... Nd] -> [log1(N) ... logN(N)]
              9fmO   e# Round each logarithm to 9 decimals.
                  &  e# Intersect this array with [1.0 ... Nd].
                   p e# Print the result.

Рубин, 50

->n{(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||p(i)}}

Печать на экране.

Рубин, 57

->n{a=[]
(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||a<<i}
a}

Возвращает массив.

В тестовой программе:

f=->n{(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||puts(i)}}

g=->n{a=[]
(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||a<<i}
a}

f.call(4096)
puts g.call(4096)

Вычисляет каждый корень и проверяет их по модулю 1, чтобы увидеть, если остаток меньше, чем 1e-8. Из-за ограниченной точности некоторые действительные целочисленные корни вычисляются как форма 0.9999 .., следовательно, необходимо добавить к ним 1e-9.

До n-го корня из n вычисляется, что является полным перебором, но, казалось, самый короткий способ написать бесконечный цикл.

Stax , 6 байт

£ÅeÉåC

Запустите и отладьте его

Все делители gcd показателей степени в простой факторизации. Это так же, как алгоритм желе.

DC, 104 байта

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

Потому что это использует? оператор, вам нужно использовать dc -e "<solution>"или dc <file with solution in it>.

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

1sb?sn[lesi]ss[lble1+dse^dln=sln>c]sc[liSflq1+sq]sm[Lfplq1-dsq0<p]dsp[lb1+sb0si0selcxli0!=mlbln!=h]dshxx

начальный материал

1sb           Store 1 in register b
?sn           Store user input in register n
[lesi]ss      A macro to copy the e to the i register, stored in the s register

Макро, чтобы поднять основание для всех сил, пока результат не больше, чем мишень или равен мишени

[lble1+dse^dln=sln>c]sc
[lb                 ]   load our base num (register b)
[  le               ]   load our exponent (register e)
[    1+dse          ]   add 1 to the exponent, copy and store in the e register
[         ^d        ]   raise the base to the exponent and copy it
[           ln=s    ]   load the user input, if that is equal to the power result run the macro in register s
[               ln>c]   load the user input, if it's greater than the power result run the macro in register c (this one)
[                   ]sc save this macro in register c

Макрос для сохранения допустимого значения экспоненты, найденного из вышеупомянутых макрокоманд экспоненты, в другой стек

[liSflq1+sq]sm
[liSf      ]     copy the i register to the top of the stack in register f
[    lq1+sq]     add 1 to the q register
[          ]sm   save this macro in the m register

Макро запустить 2x выше макро (макро) с помощью всех баз от 2 до нашего целевого числа

[lb1+sb0si0selcxli0!=mlbln!=h]dsh
[lb1+sb                      ]     add 1 to the base number
[      0si0se                ]     reset the i and e registers (previously found value and exponent
[            lcx             ]     load and run the c macro
[               li0!=m       ]     load the result of the c macro and if it's not 0, run m to save it to the f stack
[                     lbln!=h]     if our base number is not equal to our target number, run macro h (this macro)
[                            ]dsh  duplicate this macro and save one copy, so that one is left on the stack to run later

Macro для печати значения из стека ф

[Lfplq1-dsq0<p]dsp
[Lfp          ]      load the top value from the f register and print it
[   lq1-dsq   ]      load the q register and subtract one from it and save it
[          0<p]      if the q register is greater than 0, run macro p (this macro) again
[             ]dsp   duplicate this macro and save one copy, so that one is left on the stack to run later

xx finally run the two macros on the stack (h and then p)

Рубин , 46 байт

$n$$e$$b$$b^e=n$

->n{(0..n).select{|e|(1..n).find{|b|b**e==n}}}

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

C # (интерактивный компилятор Visual C #) , 93 байта

g=n=>Enumerable.Range(1,n);
f=n=>g(n).SelectMany(x=>g(n).Where(y=>(Math.Pow(x,y)==n))).Reverse()

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

Japt , 10 байт

õ
f@mpX øN

Попытайся

õ            :Implicit input of integer U
õ            :Range [1,U]
f@mpX øN     :Reassign to U
f            :Filter
 @           :By passing each X through the following function
  m          :  Map U
   pX        :    Raise to the power of X
      ø      :  Contains
       N     :    Any element of the (singelton) array of inputs