Вызов

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

Определение

Совершенная сила определяется как число, которое я нашел m ^ k , где:

• м и я натуральные числа
• м! = к

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

вход -> выход
1000 -> 16, 64, 81, 256, 512, 625, 729
56 -> 16
999 -> 16, 64, 81, 256, 512, 625, 729
81 -> 16, 64, 81
1500 -> 16, 64, 81, 256, 512, 625, 729, 1024, 1296

Пожалуйста, предоставьте читаемую, закомментированную версию.

Mathematica: 103 символа

Пробелы могут быть удалены

Select[Flatten@
       Table[
        Solve[Log@#/Log@b == k, k, Integers] /. k -> #, {b, 2, #}] & /@ Range@#, 
Length@# > 2 &][[All, 1, 1]] &  

Использование:

%[81]
{16, 64, 81}

Желе , 11 значащих байтов, вызов языковых постдат

ḊḟÆR *@þ Ḋ  F  fḊ

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

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

Вот как это работает. Ḋ(который появляется несколько раз) представляет собой список чисел от 2 до ввода включительно:

ḊḟÆR *@þ Ḋ  F  fḊ
ḊḟÆR                Ḋ, with all primes between 2 and the input removed
                    (i.e. all composite numbers from 4 to the input)
     *@þ Ḋ          Exponentiate all Ḋ elements with all ḊḟÆR elements
            F       Flatten the result (it had a nested structure)
               fḊ   Keep only elements in Ḋ

Основное наблюдение здесь состоит в том, что число является совершенной степенью во многих отношениях, только если это совершенная сила со сложным показателем (это не 1). Мы генерируем список тех, где основание от 2 до входа, а показатель степени является составным числом от 4 до входа; это действительно медленно, потому что генерирует действительно большие числа, и все они являются ответом на вопрос. Тогда мы оставляем только те ответы, которые находятся в пределах досягаемости.

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

Perl: 68 символов

Получает максимум (1000) в $N и возвращает ответ в @a.

for $x ( 2..$N ) {
    $c{$x**$_}++ for 2..log($N)/log$x
}
@a = grep { $c{$_} > 1 } keys %c

Для всей программы мне нужно еще 18 символов:

$m = shift;
for $x ( 2..$m ) {
    $c{$x**$_}++ for 2..log($m)/log$x
}
print join ' ', grep { $c{$_} > 1 } keys %c

Рубин - 101 символ (без пробелов)

f=->l{c=Hash.new{0}
2.upto(1E4){|i|2.upto(20){|j|c[i**j]+=1}}
c.map{|k,v|v>1&&k<=l&&k||p}.compact.sort}

Работает в 1 <= limit <= 100,000,000течение 5 секунд.

Тестовое задание

> f[10000]
[16, 64, 81, 256, 512, 625, 729, 1024, 1296, 2401, 4096, 6561, 10000]

Желе , 13 значимых персонажей, языковые испытания

R  µ  ọḊ *@Ḋ ċ >2  µ  Ðf

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

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

Вот как это работает:

R  µ  ọḊ *@Ḋ ċ >2  µ  Ðf
R                     Ðf    Find all numbers n from 1 to the input, such that:
   µ               µ          (grouping marks, like {} in C)
       Ḋ   Ḋ                  Take the range from 2 to n
      ọ                       Find the number of times each divides n
         *@                   Raise the range from 2 to n to these powers
             ċ                Count the number of times n appears
               >2             and the result must be greater than 2

Так, например, при тестировании n = 256 мы проверяем, сколько раз каждое из чисел от 2 до 256 делится на 256. Единственные числа, которые делятся более одного раза, это 2 (что делит 8 раз), 4 (что делит 4 раз), 8 (который делит в два раза) и 16 (который делит в два раза). Поэтому, когда мы увеличиваем число делений до определенных там полномочий, мы получаем:

2⁸, 3, 4⁴, 5, 6, 7, 8², 9, 10, 11, 12, 13, 14, 15, 16², 17, ..., 255, 256

Это дает исходное значение 256, число раз равное тому, что 256 является идеальной степенью плюс один (последний элемент выдает 256, потому что 256 = 256¹). Таким образом, если мы видим 256 в массиве более двух раз (и мы видим в этом случае; 8 ² - 64, но все остальные «интересные» элементы выдают 256), это должно быть совершенной силой.