Если задано целое число N > 1, выведите все остальные числа, простые разложения которых имеют те же цифры, что и простое разложение N.

Например, если N = 117, то вывод должен быть [279, 939, 993, 3313, 3331], потому что

117 = 3 × 3 × 13

Таким образом, имеющиеся цифры 1, 3, 3и 3и мы имеем

279  = 3 × 3 × 31
939  = 3 × 313
993  = 3 × 331
3313 = 3313
3331 = 3331

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

Если Nкакие - либо из 117, 279, 939, 993, 3313или 3331, то выход будет содержать пять других чисел: они являются главными факторами приятелями.

Вы не можете использовать начальные нули для получения простых чисел, например, для N = 107, его единственный собеседник 701( 017не рассматривается).

Вход и выход

• Входные и выходные друзья должны быть взяты и возвращены в десятичной основе.

• Nвсегда будет строго больше, чем 1.

• Вывод может быть отформатирован довольно свободно, если он содержит только синтаксические элементы «список друзей» и «разделители / список».

• Порядок вывода не важен.

• Вы можете принять ввод через STDINаргумент функции или что-то подобное.

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

Контрольные примеры

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

N        Buddies
2        []
4        []
8        []
15       [53]
16       []
23       [6]
42       [74, 146, 161]
126      [222, 438, 483, 674, 746, 851, 1466, 1631, 1679]
204      [364,548,692,762,782,852,868,1268,1626,2474,2654,2921,2951,3266,3446,3791,4274,4742,5426,5462,6233,6434,6542,7037,8561,14426,14642,15491,15833,22547]

счет

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

Желе , 14 байт

ÆfVṢṚḌ
ÇÇ€=ÇTḟ

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

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

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

ÆfVṢṚḌ   Helper link. Argument: k (integer)

Æf       Decompose k into an array of primes with product k.
  V      Eval. Eval casts a 1D array to string first, so this computes the integer
         that results of concatenating all primes in the factorization.
   Ṣ     Sort. Sort casts a number to the array of its decimal digits.
    Ṛ    Reverse. This yields the decimal digits in descending order.
     Ḍ   Undecimal; convert the digit array from base 10 to integer.


ÇÇ€=ÇTḟ  Main link. Argument: n (integer)

Ç        Call the helper link with argument n.
         This yields an upper bound (u) for all prime factorization buddies since
         the product of a list of integers cannot exceed the concatenated integers.
 ǀ      Apply the helper link to each k in [1, ..., u].
    Ç    Call the helper link (again) with argument n.
   =     Compare each result to the left with the result to the right.
     T   Truth; yield all 1-based indices of elements of [1, ..., u] (which match
         the corresponding integers) for which = returned 1.
      ḟ  Filter; remove n from the indices.

PowerShell v3 +, 450 байт

param($n)function f{param($a)for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}
$y=($x=@((f $n)-split'(.)'-ne''|sort))|?{$_-eq(f $_)}
$a,$b=$x
$a=,$a
while($b){$z,$b=$b;$a=$a+($a+$y|%{$c="$_";0..$c.Length|%{-join($c[0..$_]+$z+$c[++$_..$c.Length])};"$z$c";"$c$z"})|select -u}
$x=-join($x|sort -des)
$l=@();$a|?{$_-eq(f $_)}|%{$j=$_;for($i=0;$i-le$x;$i+=$j){if(0-notin($l|%{$i%$_})){if(-join((f $i)-split'(.)'|sort -des)-eq$x){$i}}}$l+=$j}|?{$_-ne$n}

В заключение!

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

PS C:\Tools\Scripts\golfing> Measure-Command {.\prime-factors-buddies.ps1 204}

Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 27
Milliseconds      : 114
Ticks             : 271149810
TotalDays         : 0.000313830798611111
TotalHours        : 0.00753193916666667
TotalMinutes      : 0.45191635
TotalSeconds      : 27.114981
TotalMilliseconds : 27114.981

объяснение

Здесь много чего происходит, поэтому я постараюсь разбить его.

Первая линия принимает входной сигнал $nи определяет function, f. Эта функция использует накопительное пробное деление, чтобы составить список основных факторов. Это довольно быстро для небольших входов, но, очевидно, замедляется, если вход большой. К счастью, все тесты маленькие, поэтому этого достаточно.

В следующей строке указываются fдействующие лица $n, которые -splitна каждой цифре игнорируют любые пустые результаты (это необходимо из-за того, как PowerShell выполняет сопоставление регулярных выражений и как он перемещает указатель по входным данным и является своего рода раздражающим для целей игры в гольф), а затем sortрезультаты в порядке возрастания Мы сохраняем этот массив цифр $xи используем его в качестве входных данных для |?{...}фильтра, чтобы вытащить только те, которые сами являются простыми. Эти простые цифры сохраняются $yдля последующего использования.

Затем мы разделились $xна две составляющие. Первая (т.е. самая маленькая) цифра сохраняется в $a, а остальные передаются в $b. Если $xесть только одна цифра, то $bбудет пустым / пустым. Затем нам нужно выполнить повторное приведение $aв виде массива, поэтому мы используем оператор запятой, как для быстрого перехода.

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

До тех пор, пока остается элемент $b, мы удаляем первую цифру $zи оставляем в ней $b. Затем нам нужно накапливаться в $aрезультате нарезки строк и нарезки кубиками. Мы берем в $a+$yкачестве конкатенации массивов, и для каждого элемента мы создаем новую строку $c, затем перебираем $c's' .lengthи вставляем $zв каждую позицию, включая добавление $z$cи добавление $c$z, затем добавляя selectтолько -uэлементы nique. Это снова связано с массивом $aи снова сохранено в $a. Да, это приводит к тому, что происходят глупые вещи, как вы можете получить 3333для ввода117, который на самом деле не является перестановкой, но это намного короче, чем попытка явно отфильтровать их, гарантирует, что мы получим каждую перестановку, и только очень незначительно медленнее.

Итак, теперь $aесть массив всех возможных (а затем и некоторых) перестановок цифр фактора. Нам нужно переустанавливать $xнашу верхнюю границу возможных результатов, вводя |sortцифры в -desпорядке убывания и -joinвозвращая их вместе. Очевидно, что никакое выходное значение не может быть больше этого числа.

Мы устанавливаем наш вспомогательный массив $lкак массив значений, которые мы видели ранее. Затем мы извлекаем каждое значение из $a(то есть, тех перестановок), которые являются простыми, и вводим цикл, который является самым большим временным поглотителем всей программы ...

На каждой итерации мы переходим 0к нашей верхней границе $x, увеличивая текущий элемент $j. Пока $iзначение, которое мы рассматриваем, не кратно предыдущему значению (это 0-notin($l|%{$i%$_})раздел), это потенциальный кандидат на вывод. Если взять fактеров $i, sortих, и они -eqUAL $x, а затем добавить значение к трубопроводу. В конце цикла мы добавляем наш текущий элемент $jв наш $lмассив для использования в следующий раз, так как мы уже рассмотрели все эти значения.

Наконец, мы выбираем |?{$_-ne$n}те, которые не являются элементом ввода. Они все остались на конвейере и вывод неявный.

Примеры

PS C:\Tools\Scripts\golfing> 2,4,8,15,16,23,42,117,126,204|%{"$_ --> "+(.\prime-factors-buddies $_)}
2 --> 
4 --> 
8 --> 
15 --> 53
16 --> 
23 --> 6
42 --> 74 146 161
117 --> 279 939 993 3313 3331
126 --> 222 438 674 746 1466 483 851 1679 1631
204 --> 782 2921 3266 6233 3791 15833 2951 7037 364 868 8561 15491 22547 852 762 1626 692 548 1268 2654 3446 2474 5462 4742 5426 4274 14426 6542 6434 14642

CJam , 26 23 байта

{_mfs$:XW%i){mfs$X=},^}

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

объяснение

Объединение двух чисел всегда дает больший результат, чем их умножение. Таким образом, наибольшее число, которое мы, возможно, должны рассмотреть, является наибольшим числом, которое мы можем сформировать из цифр первичной факторизации ввода, то есть просто всех цифр, отсортированных в порядке убывания. Для заданных чисел эта верхняя граница достаточно мала, чтобы мы могли тщательно проверить каждое число в диапазоне на предмет того, является ли он главным фактором:

_mf    e# Duplicate input N and get a list of its prime factors.
s$     e# Convert the list to a (flattened) string and sort it.
:X     e# Store this in X for later.
W%     e# Reverse it. This is now a string repesentation of the largest 
       e# possible output M.
i)     e# Convert to integer and increment.
{      e# Get a list of all integers i in [0 1 ... M] for which the following
       e# block gives a truthy result.
  mf   e#   Get list of prime factors of i.
  s$   e#   Get a sorted list of the digits appearing in the factorisation.
  X=   e#   Check for equality with X.
},
^      e# Symmetric set difference: removes N from the output list.

05AB1E , 17 байт

Код:

ÒJ{©RƒNÒJ{®QN¹Ê*–

Объяснение:

Ò                  # Get the factorization with duplicates, e.g. [3, 3, 13]
 J                 # Join the array, e.g. 3313
  {©               # Sort and store in ©, e.g. 1333
    R              # Reverse the number, e.g. 3331. This is the upperbound for the range
     ƒ             # For N in range(0, a + 1), do...
      NÒ           # Push the factorization with duplicates for N
        J          # Join the array
         {         # Sort the string
          ®Q       # Check if equal to the string saved in ©
            N¹Ê    # Check if not equal to the input
               *   # Multiply, acts as a logical AND
                –  # If 1, print N

Использует кодировку CP-1252 . Попробуйте онлайн!

Пиф, 17

LSjkPb-fqyTyQSs_y

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

Использует то же наблюдение, что и из поста Мартина .

Расширение:

LSjkPb        ##  Define a function y(b) to get the sorted string of digits
              ##  of the prime factors of b
    Pb        ##  prime factors
  jk          ##  join to a string with no separator
 S            ##  Sort

-fqyTyQSs_yQQ ##  Auto-fill variables
         _yQ  ##  get reversed value of y(input)
       Ss     ##  convert that string to a list [1 ... y(input)]
 fqyTyQ       ##  keep numbers T from the list that satisfy y(T)==y(input)
-           Q ##  remove the input from the result

JavaScript (ES6), 163 158 байт

Редактировать : было разъяснено, что простое число, такое как 23, должно возвращать [6] скорее пустой набор результатов. Сэкономили 5 байт, удалив теперь бесполезное правило, которое специально было предотвращено.

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

let f =

n=>[...Array(+(l=(p=n=>{for(i=2,m=n,s='';i<=m;n%i?i++:(s+=i,n/=i));return s.split``.sort().reverse().join``})(n))+1)].map((_,i)=>i).filter(i=>i&&i-n&&p(i)==l)

console.log(JSON.stringify(f(2)));
console.log(JSON.stringify(f(4)));
console.log(JSON.stringify(f(8)));
console.log(JSON.stringify(f(15)));
console.log(JSON.stringify(f(16)));
console.log(JSON.stringify(f(23)));
console.log(JSON.stringify(f(42)));
console.log(JSON.stringify(f(126)));
//console.log(JSON.stringify(f(204)));

PHP 486 байт

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

function p($n){for($i=1;$i++<$n;)if($n%$i<1&&($n-$i?p($i)==$i:!$r))for($x=$n;$x%$i<1;$x/=$i)$r.=$i;return $r;}function e($s){if(!$n=strlen($s))yield$s;else foreach(e(substr($s,1))as$p)for($i=$n;$i--;)yield substr($p,0,$i).$s[0].substr($p,$i);}foreach(e(p($n=$argv[1]))as$p)for($m=1<<strlen($p)-1;$m--;){$q="";foreach(str_split($p)as$i=>$c)$q.=$c.($m>>$i&1?"*":"");foreach(split("\*",$q)as$x)if(0===strpos($x,48)|p($x)!=$x)continue 2;eval("\$r[$q]=$q;");}unset($r[$n]);echo join(",",$r);

сломать

// find and concatenate prime factors
function p($n)
{
    for($i=1;$i++<$n;)  // loop $i from 2 to $n
        if($n%$i<1      // if $n/$i has no remainder
            &&($n-$i    // and ...
                ?p($i)==$i  // $n!=$i: $i is a prime
                :!$r        // $n==$i: result so far is empty ($n is prime)
            )
        )
            for($x=$n;      // set $x to $n
                $x%$i<1;    // while $x/$i has no remainder
                $x/=$i)     // 2. divide $x by $i
                $r.=$i;     // 1. append $i to result
    return $r;
}

// create all permutations of digits
function e($s)
{
    if(!$n=strlen($s))yield$s;else  // if $s is empty, yield it, else:
    foreach(e(substr($s,1))as$p)    // for all permutations of the number w/o first digit
        for($i=$n;$i--;)            // run $i through all positions around the other digits
            // insert removed digit at that position and yield
            yield substr($p,0,$i).$s[0].substr($p,$i);
}

// for each permutation
foreach(e(p($n=$argv[1]))as$p)
    // create all products from these digits: binary loop through between the digits
    for($m=1<<strlen($p)-1;$m--;)
    {
        // and insert "*" for set bits
        $q="";
        foreach(str_split($p)as$i=>$c)$q.=$c.($m>>$i&1?"*":"");
        // test all numbers in the expression
        foreach(split("\*",$q)as$x)
            if(
                0===strpos($x,48)   // if number has a leading zero
                |p($x)!=$x          // or is not prime
            )continue 2; // try next $m
        // evaluate expression and add to results (use key to avoid array_unique)
        eval("\$r[$q]=$q;");
    }

// remove input from results
unset($r[$n]);

// output
#sort($r);
echo join(",",$r);

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

При этом используется тот же алгоритм, который использовали Martin , Adnan , FryAmTheEggman и Dennis . Предложения по игре в гольф приветствуются. Попробуйте онлайн!

`w"i$n"£MΣSR≈`╗╜ƒ;╝R`╜ƒ╛=`░

Ungolfing

          Implicit input n.
`...`╗    Define a function and store it in register 0. Call the function f(x).
  w         Get the prime factorization of x.
  "..."£M   Begin another function and map over the [prime, exponent] lists of w.
    i         Flatten the list. Stack: prime, exponent.
    $n        Push str(prime) to the stack, exponent times.
               The purpose of this function is to get w's prime factors to multiplicity.
  Σ         sum() the result of the map.
             On a list of strings, this has the same effect as "".join()
  SR≈       Sort that string, reverse it and convert to int.
╜ƒ        Now push the function stored in register 0 and call it immediately.
           This gives the upper bound for any possible prime factor buddy.
;╝        Duplicate this upper bound and save a copy to register 1.
R         Push the range [0..u]
`...`░    Filter the range for values where the following function returns a truthy.
           Variable k.
  ╜ƒ        Push the function in register 0 and call it on k.
  ╛=        Check if f(k) == f(n).
          Implicit return every value that is a prime factor buddy with n, including n.

Powershell, 147 байт (версия CodeGolf)

param($n)filter d{-join($(for($i=2;$_-ge$i*$i){if($_%$i){$i++}else{"$i"
$_/=$i}}if($_-1){"$_"})|% t*y|sort -d)}2..($s=$n|d)|?{$_-$n-and$s-eq($_|d)}

Примечание. Скрипт решает последние тестовые задания менее чем за 3 минуты в моей локальной записной книжке. Смотрите решение «производительность» ниже.

Менее гольф тестовый скрипт:

$g = {

param($n)
filter d{                       # in the filter, Powershell automatically declares the parameter as $_
    -join($(                    # this function returns a string with all digits of all prime divisors in descending order
        for($i=2;$_-ge$i*$i){   # find all prime divisors
            if($_%$i){
                $i++
            }else{
                "$i"            # push a divisor to a pipe as a string
                $_/=$i
            }
        }
        if($_-1){
            "$_"                # push a last divisor to pipe if it is not 1
        }
    )|% t*y|sort -d)            # t*y is a shortcut to toCharArray method. It's very slow.
}
2..($s=$n|d)|?{                 # for each number from 2 to number with all digits of all prime divisors in descending order
    $_-$n-and$s-eq($_|d)        # leave only those who have the 'all digits of all prime divisors in descending order' are the same
}

}

@(
    ,(2   ,'')
    ,(4   ,'')
    ,(6   ,23)
    ,(8   ,'')
    ,(15  ,53)
    ,(16  ,'')
    ,(23  ,6)
    ,(42  ,74, 146, 161)
    ,(107 ,701)
    ,(117 ,279, 939, 993, 3313, 3331)
    ,(126 ,222, 438, 483, 674, 746, 851, 1466, 1631, 1679)
    ,(204 ,364,548,692,762,782,852,868,1268,1626,2474,2654,2921,2951,3266,3446,3791,4274,4742,5426,5462,6233,6434,6542,7037,8561,14426,14642,15491,15833,22547)
) | % {
    $n,$expected = $_

    $sw = Measure-Command {
        $result = &$g $n
    }

    $equals=$false-notin(($result|%{$_-in$expected})+($expected|?{$_-is[int]}|%{$_-in$result}))
    "$sw : $equals : $n ---> $result"
}

Выход:

00:00:00.0346911 : True : 2 --->
00:00:00.0662627 : True : 4 --->
00:00:00.1164648 : True : 6 ---> 23
00:00:00.6376735 : True : 8 --->
00:00:00.1591527 : True : 15 ---> 53
00:00:03.8886378 : True : 16 --->
00:00:00.0441986 : True : 23 ---> 6
00:00:01.1316642 : True : 42 ---> 74 146 161
00:00:01.0393848 : True : 107 ---> 701
00:00:05.2977238 : True : 117 ---> 279 939 993 3313 3331
00:00:12.1244363 : True : 126 ---> 222 438 483 674 746 851 1466 1631 1679
00:02:50.1292786 : True : 204 ---> 364 548 692 762 782 852 868 1268 1626 2474 2654 2921 2951 3266 3446 3791 4274 4742 5426 5462 6233 6434 6542 7037 8561 14426 14642 15491 15833 22547

Powershell, 215 байт (версия «Performance»)

param($n)$p=@{}
filter d{$k=$_*($_-le3e3)
($p.$k=-join($(for($i=2;!$p.$_-and$_-ge$i*$i){if($_%$i){$i++}else{"$i"
$_/=$i}}if($_-1){($p.$_,"$_")[!$p.$_]})-split'(.)'-ne''|sort -d))}2..($s=$n|d)|?{$_-$n-and$s-eq($_|d)}

Примечание: я считаю, что требования к производительности противоречат принципу GodeGolf. Но поскольку существовало правило Your program should solve any of the test cases below in less than a minute, я внес два изменения, чтобы удовлетворить этому правилу:

• -split'(.)'-ne''вместо краткого кода |% t*y;
• хеш-таблица для обналичивания строк.

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

Менее гольф тестовый скрипт:

$g = {

param($n)
$p=@{}                          # hashtable for 'all digits of all prime divisors in descending order'
filter d{                       # this function returns a string with all digits of all prime divisors in descending order
    $k=$_*($_-le3e3)            # hashtable key: a large hashtable is not effective, therefore a key for numbers great then 3000 is 0
                                # and string '-le3e3' funny
    ($p.$k=-join($(             # store the value to hashtable
        for($i=2;!$p.$_-and$_-ge$i*$i){
            if($_%$i){$i++}else{"$i";$_/=$i}
        }
        if($_-1){
            ($p.$_,"$_")[!$p.$_] # get a string with 'all digits of all prime divisors in descending order' from hashtable if it found
        }
    )-split'(.)'-ne''|sort -d)) # split each digit. The "-split'(.)-ne''" code is faster then '|% t*y' but longer.
}
2..($s=$n|d)|?{                 # for each number from 2 to number with all digits of all prime divisors in descending order
    $_-$n-and$s-eq($_|d)        # leave only those who have the 'all digits of all prime divisors in descending order' are the same
}

}

@(
    ,(2   ,'')
    ,(4   ,'')
    ,(6   ,23)
    ,(8   ,'')
    ,(15  ,53)
    ,(16  ,'')
    ,(23  ,6)
    ,(42  ,74, 146, 161)
    ,(107 ,701)
    ,(117 ,279, 939, 993, 3313, 3331)
    ,(126 ,222, 438, 483, 674, 746, 851, 1466, 1631, 1679)
    ,(204 ,364,548,692,762,782,852,868,1268,1626,2474,2654,2921,2951,3266,3446,3791,4274,4742,5426,5462,6233,6434,6542,7037,8561,14426,14642,15491,15833,22547)
) | % {
    $n,$expected = $_

    $sw = Measure-Command {
        $result = &$g $n
    }

    $equals=$false-notin(($result|%{$_-in$expected})+($expected|?{$_-is[int]}|%{$_-in$result}))
    "$sw : $equals : $n ---> $result"
}

Выход:

00:00:00.0183237 : True : 2 --->
00:00:00.0058198 : True : 4 --->
00:00:00.0181185 : True : 6 ---> 23
00:00:00.4389282 : True : 8 --->
00:00:00.0132624 : True : 15 ---> 53
00:00:04.4952714 : True : 16 --->
00:00:00.0128230 : True : 23 ---> 6
00:00:01.4112716 : True : 42 ---> 74 146 161
00:00:01.3676701 : True : 107 ---> 701
00:00:07.1192912 : True : 117 ---> 279 939 993 3313 3331
00:00:07.6578543 : True : 126 ---> 222 438 483 674 746 851 1466 1631 1679
00:00:50.5501853 : True : 204 ---> 364 548 692 762 782 852 868 1268 1626 2474 2654 2921 2951 3266 3446 3791 4274 4742 5426 5462 6233 6434 6542 7037 8561 14426 14642 15491 15833 22547

Japt, 18 байт

k –
Ôn õ f@¥Xk ¬ñ

Попытайся