Biorąc pod uwagę liczbę całkowitą N > 1, wypisz wszystkie pozostałe liczby, których podstawowy rozkład ma te same cyfry, co pierwotny rozkład N.

Na przykład, jeśli N = 117, to wynik musi być [279, 939, 993, 3313, 3331], ponieważ

117 = 3 × 3 × 13

Dlatego dostępne są cyfry 1, 3, 3a 3i mamy

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

Są to jedyne możliwe liczby, ponieważ inna kombinacja tych cyfr daje liczby całkowite inne niż pierwotne, co nie może być wynikiem faktoryzacji liczby pierwszej.

Jeśli Njakakolwiek z 117, 279, 939, 993, 3313lub 3331, następnie wyjście będzie zawierać pięć innych numerów: są czynniki pierwsze kumple.

Nie można używać zer wiodących, aby uzyskać liczby pierwsze, np. N = 107Jego jedyny znajomy to 701( 017nie jest brany pod uwagę).

Wejścia i wyjścia

• Dane wejściowe i wyjściowe muszą zostać pobrane i zwrócone w postaci dziesiętnej.

• Nzawsze będzie zdecydowanie większy niż 1.

• Dane wyjściowe mogą być formatowane raczej swobodnie, pod warunkiem, że zawierają tylko elementy znajomych i separatory / elementy składniowe listy.

• Kolejność danych wyjściowych jest nieistotna.

• Możesz wziąć dane wejściowe STDINjako argument funkcji lub coś podobnego.

• Możesz wydrukować dane wyjściowe STDOUT, zwrócić je z funkcji lub coś podobnego.

Przypadki testowe

Twój program powinien rozwiązać dowolny z poniższych przypadków testowych w mniej niż minutę .

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]

Punktacja

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.

Galaretka , 14 bajtów

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

Czas wykonania można zmniejszyć o połowę DFzamiast V, ale nadal kończy połączone przypadki testowe w niecałe trzydzieści sekund.

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

Æ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 bajtów

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}

Wreszcie!

Program PowerShell nie ma żadnych wbudowanych funkcji sprawdzania pierwotności, faktoryzacji ani permutacji, więc jest to całkowicie ręcznie. Przeszedłem przez szereg sztuczek optymalizacyjnych, aby zmniejszyć złożoność czasu do poziomu, który będzie pasował do ograniczeń wyzwania, i cieszę się, że w końcu udało mi się -

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

Wyjaśnienie

Dużo się tu dzieje, więc spróbuję to zepsuć.

Pierwsza linia zajmuje wejście $ni określa function, f. Ta funkcja wykorzystuje kumulatywny podział prób, aby uzyskać listę głównych czynników. Jest dość szybki dla małych wejść, ale oczywiście zapada się, jeśli wejście jest duże. Na szczęście wszystkie przypadki testowe są małe, więc to wystarczy.

Następna linia dostaje faktorów $n, -splits je na każdej cyfry ignorowania pustych wyników (jest to konieczne ze względu na to, jak PowerShell robi regex dopasowywania i jak przesuwa wskaźnik przez wejście i jest trochę irytujące dla celów golfa), a następnie sorts wyniki w porządku rosnącym. Przechowujemy tę tablicę cyfr $xi używamy jej jako danych wejściowych do |?{...}filtra, aby wyciągnąć tylko te, które same są pierwsze. Te pierwsze cyfry są przechowywane w $ycelu późniejszego użycia.

Następnie podzieliliśmy się $xna dwa składniki. Pierwsza (tj. Najmniejsza) cyfra jest zapisywana $a, a pozostałe są przekazywane $b. Jeśli $xma tylko jedną cyfrę, wówczas $bbędzie pusta / null. Następnie musimy ponownie rzutować $ajako tablicę, więc używamy do tego szybkiego operatora przecinka.

Następnie musimy skonstruować wszystkie możliwe kombinacje cyfr. Jest to konieczne, więc nasze testy podziału pomijają później kilka liczb i ogólnie przyspieszają.

Tak długo, jak pozostanie element $b, odklejamy pierwszą cyfrę $zi pozostawiamy pozostałą $b. Następnie musimy kumulować się $aw wyniku niektórych cięć i krojenia sznurków. Weźmiemy $a+$yw tablicy konkatenacji, a każdy element skonstruowano nowy łańcuch $c, a następnie za pomocą pętli $cjest .lengthi wkładką $zw każdej pozycji, w tym poprzedzenie $z$ci dołączanie $c$z, a selectnia tylko -uNique elementy. To jest ponownie połączone z macierzą $ai ponownie zapisane w $a. Tak, kończy się to, że głupie rzeczy się zdarzają, tak jakbyś mógł uzyskać 3333wkład117, co w rzeczywistości nie jest permutacją, ale jest to znacznie krótsze niż próba ich jawnego odfiltrowania, zapewnia, że ​​otrzymujemy każdą permutację i jest tylko bardzo nieznacznie wolniejsza.

Tak więc teraz $ama tablicę wszystkich możliwych (a następnie niektórych) permutacji cyfr czynnika. Musimy zresetować, $xaby być naszą górną granicą możliwych wyników, łącząc |sortcyfry w -deskolejności nadawania i -joinłącząc je z powrotem. Oczywiście żadna wartość wyjściowa nie może być większa niż ta liczba.

Ustawiliśmy naszą tablicę pomocniczą $ljako tablicę wartości, które wcześniej widzieliśmy. Następnie wyciągamy każdą wartość z $a(tj. Tych permutacji), które są liczbą pierwszą, i wchodzimy do pętli, która jest największym ujściem czasowym całego programu ...

Podczas każdej iteracji zapętlamy się 0do górnej granicy $x, zwiększając o bieżący element $j. Tak długo, jak $irozważana wartość nie jest wielokrotnością poprzedniej wartości (to 0-notin($l|%{$i%$_})sekcja), jest potencjalnym kandydatem na wynik. Jeśli weźmiemy faktorzy $i, sortoni i oni są -eqprzekonani $x, dodaj wartość do rurociągu. Na końcu pętli dodajemy nasz bieżący element $jdo naszej $ltablicy, aby użyć go następnym razem, ponieważ rozważaliśmy już wszystkie te wartości.

Wreszcie staramy |?{$_-ne$n}się wyciągać te, które nie są elementem wejściowym. Wszystkie pozostały w przygotowaniu, a dane wyjściowe są niejawne.

Przykłady

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 bajtów

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

Wypróbuj online

Wyjaśnienie

Łączenie dwóch liczb zawsze daje większy wynik niż pomnożenie ich. Zatem największa liczba, którą prawdopodobnie powinniśmy wziąć pod uwagę, to największa liczba, jaką możemy utworzyć z cyfr pierwszego podziału na czynniki pierwsze, czyli wszystkie cyfry posortowane w porządku malejącym. Dla podanych liczb górna granica jest wystarczająco mała, abyśmy mogli wyczerpująco sprawdzić każdą liczbę w zakresie, czy jest to kolega z czynnika pierwszego:

_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 bajtów

Kod:

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

Wyjaśnienie:

Ò                  # 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

Wykorzystuje kodowanie CP-1252 . Wypróbuj online!

Pyth, 17 lat

LSjkPb-fqyTyQSs_y

Zestaw testowy .

Używa tej samej obserwacji, co post Martina .

Ekspansja:

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 bajtów

Edytować : Wyjaśniono, że liczba pierwsza, taka jak 23, powinna zwrócić [6] raczej pusty zestaw wyników. Zaoszczędzono 5 bajtów, usuwając teraz bezużyteczną regułę, która - celowo - zapobiegała temu.

Ostatni przypadek testowy został skomentowany, aby ten fragment działał wystarczająco szybko, chociaż powinien również zostać ukończony w mniej niż minutę.

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 bajtów

może być krótszy z algorytmem, którego nie ma w książce.
(ale podoba mi się bieżąca liczba bajtów)

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);

awaria

// 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);

Właściwie 27 bajtów

Wykorzystuje ten sam algorytm , którego używali Martin , Adnan , FryAmTheEggman i Dennis . Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

`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 bajtów (wersja 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)}

Uwaga: Skrypt rozwiązuje ostatnie przypadki testowe na moim lokalnym notatniku w czasie krótszym niż 3 minuty. Zobacz rozwiązanie „wydajność” poniżej.

Skrypt testu mniej golfowego:

$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"
}

Wydajność:

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 bajtów (wersja „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)}

Uwaga: Uważam, że wymagania dotyczące wydajności są sprzeczne z zasadą GodeGolf. Ale ponieważ istniała reguła Your program should solve any of the test cases below in less than a minute, wprowadziłem dwie zmiany w celu jej spełnienia:

• -split'(.)'-ne''zamiast tego krótki kod |% t*y;
• hashtable do wypłat gotówki.

Każda zmiana skraca czas oceny o połowę. Nie sądzę, że wykorzystałem wszystkie funkcje do poprawy wydajności. Wystarczyły te, aby spełnić regułę.

Skrypt testu mniej golfowego:

$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"
}

Wydajność:

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 bajtów

k –
Ôn õ f@¥Xk ¬ñ

Spróbuj