Dengan bilangan bulat N > 1, hasilkan semua angka lainnya yang dekomposisi utamanya memiliki digit yang sama dengan dekomposisi utama N.

Misalnya, jika N = 117, maka outputnya harus [279, 939, 993, 3313, 3331], karena

117 = 3 × 3 × 13

oleh karena itu, tersedia angka yang 1, 3, 3dan 3dan kita harus

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

Itu adalah satu-satunya angka lain yang mungkin, karena kombinasi lain dari angka-angka ini menghasilkan bilangan bulat non-prima, yang tidak dapat menjadi hasil faktorisasi prima.

Jika Nadalah salah 117, 279, 939, 993, 3313atau3331 , maka output akan berisi lima nomor lainnya: mereka adalah faktor utama teman.

Anda tidak dapat menggunakan nol terkemuka untuk mendapatkan bilangan prima, misalnya untuk N = 107, satu-satunya teman adalah 701(017 tidak dipertimbangkan).

Input dan Output

• Teman input dan output harus diambil dan dikembalikan dalam basis desimal.

• Nakan selalu lebih ketat dari 1.

• Outputnya bisa diformat dengan bebas, asalkan hanya berisi sobat dan elemen pemisah / daftar sintaksis.

• Urutan output tidak penting.

• Anda dapat mengambil input melalui STDIN, sebagai argumen fungsi atau yang serupa.

• Anda dapat mencetak output ke STDOUT, mengembalikannya dari fungsi, atau yang serupa.

Uji kasus

Program Anda harus menyelesaikan salah satu kasus uji di bawah ini dalam waktu kurang dari satu menit .

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]

Mencetak gol

Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.

Jelly , 14 byte

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

Waktu eksekusi bisa dibagi dua dengan DFbukan V, tetapi masih melengkapi uji gabungan kasus di bawah tiga puluh detik.

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

Æ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 byte

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}

Akhirnya!

PowerShell tidak memiliki built-in untuk pengecekan primitif, faktorisasi, atau permutasi, jadi ini sepenuhnya digulung dengan tangan. Saya bekerja melalui banyak trik pengoptimalan untuk mencoba dan mengurangi kompleksitas waktu menjadi sesuatu yang sesuai dengan batasan tantangan, dan saya senang mengatakan bahwa saya akhirnya berhasil -

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

Penjelasan

Ada banyak hal yang terjadi di sini, jadi saya akan mencoba memecahnya.

Baris pertama mengambil input $ndan mendefinisikan sebuah function, f. Fungsi ini menggunakan divisi percobaan akumulatif untuk menghasilkan daftar faktor-faktor utama. Ini cukup cepat untuk input kecil, tapi jelas rawa turun jika inputnya besar. Untungnya semua test case kecil, jadi ini sudah cukup.

Baris berikutnya mendapatkan faktor $n, -splitmereka pada setiap digit mengabaikan hasil kosong (ini diperlukan karena bagaimana PowerShell melakukan pencocokan regex dan bagaimana memindahkan pointer melalui input dan agak menjengkelkan untuk tujuan bermain golf), kemudian sorthasilnya dalam urutan menaik. Kami menyimpan array angka itu ke dalam $x, dan menggunakannya sebagai input ke |?{...}filter untuk menarik hanya mereka yang prima. Digit-digit utama tersebut disimpan $yuntuk digunakan nanti.

Kami kemudian dibagi $xmenjadi dua komponen. Digit pertama (yaitu, terkecil) disimpan ke dalam $a, sedangkan sisanya dilewatkan ke $b. Jika $xhanya memiliki satu digit, maka $bakan kosong / null. Kami kemudian perlu melakukan casting ulang $asebagai array, jadi kami menggunakan operator koma seperti untuk melakukannya.

Selanjutnya, kita perlu membangun semua kemungkinan permutasi digit. Ini diperlukan agar pengujian divisi kami nanti melewati banyak angka dan membuat semuanya lebih cepat secara keseluruhan.

Selama ada elemen yang tersisa $b, kita lepaskan digit pertama ke dalam $zdan biarkan sisanya masuk $b. Kemudian, kita perlu menumpuk ke $adalam hasil dari beberapa mengiris tali dan dicing. Kami mengambil $a+$ysebagai array yang Rangkaian, dan untuk setiap elemen kita membangun string baru $c, maka loop melalui $c's .lengthdan insert $zke dalam setiap posisi, termasuk mengawali $z$cdan menambahkan $c$z, kemudian selecting hanya -uelemen nique. Itu lagi array-digabungkan dengan $adan disimpan kembali ke dalam$a . Ya, ini memang berakhir dengan hal konyol terjadi, seperti Anda bisa mendapatkan 3333masukan117, yang sebenarnya bukan permutasi, tetapi ini jauh lebih pendek daripada mencoba menyaringnya secara eksplisit, memastikan bahwa kita mendapatkan setiap permutasi, dan hanya sedikit lebih lambat.

Jadi, sekarang $amemiliki array semua permutasi yang mungkin (dan kemudian beberapa) dari digit faktor. Kita perlu mengatur ulang $xuntuk menjadi batas atas dari hasil yang mungkin dengan |sortmemasukkan angka dalam -desurutan cending dan -joinmenggabungkannya kembali. Jelas, tidak ada nilai output yang bisa lebih besar dari angka ini.

Kami menetapkan larik pembantu kami $lmenjadi larik nilai yang sebelumnya telah kami lihat. Selanjutnya, kami mengeluarkan setiap nilai dari $a(yaitu permutasi tersebut) yang prima, dan memasukkan satu loop yang merupakan waktu terbesar dari seluruh program ...

Setiap iterasi, kami beralih dari 0batas atas kami $x, bertambah dengan elemen saat ini $j. Selama $inilai yang kami pertimbangkan bukan kelipatan dari nilai sebelumnya (itulah 0-notin($l|%{$i%$_})bagiannya), itu adalah kandidat potensial untuk output. Jika kita mengambil faktor $i, sortmereka, dan mereka -equal $x, kemudian menambahkan nilai ke dalam pipa. Pada akhir loop, kami menambahkan elemen kami saat ini $jke $larray kami untuk digunakan di lain waktu, karena kami telah mempertimbangkan semua nilai tersebut.

Akhirnya, kami |?{$_-ne$n}berusaha untuk menarik keluar yang bukan elemen input. Mereka semua tertinggal di jalur pipa dan hasilnya tersirat.

Contohnya

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 byte

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

Cobalah online

Penjelasan

Menggabungkan dua angka selalu memberikan hasil yang lebih besar daripada mengalikannya. Jadi jumlah terbesar yang perlu kita pertimbangkan adalah jumlah terbesar yang dapat kita bentuk dari digit faktorisasi utama input, yang hanya semua digit yang diurutkan dalam urutan menurun. Untuk angka yang diberikan, batas atas ini cukup kecil sehingga kita dapat memeriksa setiap angka dalam rentang untuk mengetahui apakah itu faktor teman utama:

_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 byte

Kode:

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

Penjelasan:

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

Menggunakan pengkodean CP-1252 . Cobalah online!

Pyth, 17

LSjkPb-fqyTyQSs_y

Suite uji .

Menggunakan pengamatan yang sama seperti dari pos Martin .

Ekspansi:

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 byte

Edit : Telah diklarifikasi bahwa prime seperti 23 harus mengembalikan [6] dan bukannya set hasil kosong. Disimpan 5 byte dengan menghapus aturan yang sekarang tidak berguna yang - sengaja - mencegah hal itu terjadi.

Test case terakhir dikomentari sehingga snippet ini berjalan cukup cepat, meskipun harus selesai dalam waktu kurang dari satu menit juga.

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 byte

mungkin bisa lebih pendek dengan algoritma yang tidak sesuai dengan buku.
(tapi saya suka jumlah byte saat ini)

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

kerusakan

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

Sebenarnya, 27 byte

Ini menggunakan algoritma yang sama yang telah digunakan Martin , Adnan , FryAmTheEggman , dan Dennis . Saran golf diterima. Cobalah online!

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

Tidak melakukanolf

          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 byte (versi 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)}

Catatan: Script menyelesaikan kasus uji terakhir kurang dari 3 menit pada notebook lokal saya. Lihat solusi "kinerja" di bawah ini.

Skrip uji yang kurang golf:

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

Keluaran:

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 byte (versi "Kinerja")

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

Catatan: Saya percaya persyaratan kinerja bertentangan dengan prinsip GodeGolf. Tetapi karena ada aturan Your program should solve any of the test cases below in less than a minute, saya membuat dua perubahan untuk memenuhi aturan:

• -split'(.)'-ne'' alih-alih kode pendek |% t*y ;
• hashtable untuk menguangkan string.

Setiap perubahan mengurangi setengah waktu evaluasi. Tolong jangan berpikir bahwa saya telah menggunakan semua fitur untuk meningkatkan kinerja. Hanya itu saja sudah cukup untuk memenuhi aturan.

Skrip uji yang kurang golf:

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

Keluaran:

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 byte

k –
Ôn õ f@¥Xk ¬ñ

Cobalah