Faktorisasi Perdana Rekursif

8

Tugas Anda adalah mengambil faktor prima dari angka yang diambil dari input (menghilangkan eksponen yang sama dengan 1) kemudian mengambil faktor prima dari semua eksponen, dan seterusnya, hingga tidak ada angka komposit yang tersisa; dan kemudian menampilkan hasilnya.

Untuk membuat apa yang saya tanyakan sedikit lebih jelas, berikut ini adalah program javascript yang melakukannya, tetapi, pada 782 byte, ini belum golf dengan baik:

var primes=[2,3];
function nextPrime(){
    var n=2;
    while(isAMultipleOfAKnownPrime(n)){n++}
    primes.push(n);
}
function isAKnownPrime(n){return primes.indexOf(n)!=-1};
function isAMultipleOfAKnownPrime(n){
    for(var i=0;i<primes.length;i++)if(n%primes[i]==0)return true;
    return false;
}
function primeFactorize(n){
    while(primes[primes.length-1]<n)nextPrime();
    if(isAKnownPrime(n)||n==1)return n;
    var q=[];while(q.length<=n)q.push(0);
    while(n!=1){
        for(var i=0;i<primes.length;i++){
            var x=primes[i];
            if(n%x==0){q[x]++;n/=x}
        }
    }
    var o="";
    for(var i=2;i<q.length;i++){
        if(q[i]){if(o)o+="x";o+=i;if(q[i]>1){o+="^("+primeFactorize(q[i])+")"}}
    }
    return o;
}
alert(primeFactorize(+prompt()));

Anda harus membuat urutan operasi sejelas mungkin, dan mengurutkan faktor utama dalam urutan naik pada setiap level.

Anda mendapatkan bonus -50 byte jika Anda menghasilkan output sebagai matematika yang diformat atau kode lateks yang valid.

SuperJedi224
sumber
17
Ini akan membantu memberikan contoh input dan output.
DavidC
7
Bisakah Anda memberikan beberapa contoh input dan output? Saya mengalami kesulitan memahami spec Anda, dan solusi contohnya cukup singkat.
Zgarb
@ Zgarb Dia berarti faktor bilangan bulat, faktor eksponen prima, faktor eksponen mereka , dll, sampai Anda dibiarkan dengan semua bilangan prima.
LegionMammal978
2
Apa sebenarnya yang Anda pahami sebagai "sidik jari berformat". Apakah misalnya diizinkan untuk mencetak kode lateks?
Jakube
1
@Zgarb Semua format yang berfungsi (mis. 2^(5^11*11^(2^7))*541).
LegionMammal978

Jawaban:

7

CJam, 32 31 29 27 25 - 50 = -25 byte

7 byte disimpan oleh Dennis.

Woooo, Dennis mengurangi ini dengan tujuh byte yang luar biasa dan berhasil mengalahkan Pyth!

q~S2*{mF{~'^'{@j'}'*}/;}j

Uji di sini.

Penjelasan

q~                           e# Read and eval input.
  S2*                        e# Push the string "  ". The second space will be our 
                             e# memoised result for input 1. This way, 1-exponents become 
                             e# ^{ } later which do not affect the rendered output of the 
                             e# generated LaTeX.
     {                 }j    e# Initialise a recursion with the above base case.
      mF                     e# Compute prime factorisation as list of pairs.
        {           }/       e# For each pair...
         ~'^'{@              e# Unwrap the pair and put a '^' and a '{' in the middle.
               j             e# Recursively run the outer block on the exponent.
                '}'*         e# Push a '}' and a '*' character.
                      ;      e# Discard the last '*'.

Semua isi tumpukan itu akan dicetak secara otomatis kembali-ke-belakang di akhir program.

Martin Ender
sumber
"{}"-> {}sSepertinya Anda sudah menemukan cara jkerjanya.
Dennis
@ Dennis Saya pikir saya telah menggunakan juntuk sementara waktu. user23013 memposting penjelasan yang bagus tentang Konversi Basis Campuran, dan aditsu beberapa pernyataan klarifikasi untuk penggunaan lanjutan di suatu tempat di SourceForge.
Martin Ender
aditsu benar-benar menjawab posting forum saya, tetapi SF tidak memberi tahu saya dan saya berhenti memeriksa setelah beberapa bulan ... Meskipun jcukup keren, fungsi bernama akan lebih pendek di sini:{mF{)_({Fa+'^}&*}%'**{}s\*}:F
Dennis
@ Dennis Oh, benar, saya tidak menganggap bahwa saya benar-benar dapat menjadikannya sebagai pengajuan fungsi saja jika saya menggunakan pendekatan fungsi yang dinamai. Akan mengubah jawabannya nanti.
Martin Ender
1
25 byte:q~S2*{mF{~'^'{@j'}'*}/;}j
Dennis
14

Pyth, 27 - 50 = -23 byte

Lj\*m+ed?+\^jyhd`HthdkrPb8

Ini mendefinisikan fungsi rekursif y . Cobalah online: Peragaan

Outputnya adalah kode LaTeX yang valid, jadi saya mengklaim bonus. Panggilan y66430125mengembalikan string3^{2^{2}*3}*5^{3} , yang dirender menjadi

pic_small

Cukup bangga karena menemukan cara untuk mencetak kurung keriting tanpa menggunakan kurung keriting dalam kode saya.

Penjelasan:

L                            define a function y(b): return ...
                       Pb       prime factorization of b
                      r  8      run-length-encoded, gives pairs of (exponent, prime)
    m                           map each pair d (exponent, prime) to:
      ed                          prime
     +                            +
             yhd                    recursive call
            j   `H                  join repr(H) by ^
                                      H is preinitialized with an empty dictionary
                                      so the repr(H) gives the string "{}"
                                      and join inserts the prime-factorization 
                                      of the exponent between the chars of "{}"

         +\^                        add "^" at the beginning
        ?         thd               if exponent - 1 != 0 else
                     k              "" (empty string)
 j\*                            join by "*"
Jakube
sumber
1
@ SuperJedi224 Ya, benar. Menggunakan pendekatan lama yang ini lebih pendek. Tapi sekarang, setelah saya menemukan repr(H)triknya, tidak masalah. Jadi saya mengeditnya sekarang.
Jakube
By the way {}adalah kamus kosong di Python, bukan set kosong.
isaacg
6

Pyth - 39 34 32 28 byte

Terima kasih Jakube

Menentukan fungsi yyang mengambil integer:

L?j\xm+ed+"^("+yhd\)rPb8tPbb

Penjelasan:

L                              define y(b): return                                  
  j\x                              "x".join(                                        
     m                                 map(lambda d:                                
      +ed+"^("+yhd\)                       d[1] + "^(" + y(d[0]) + ")",             
                    rPb8                   tally(prime_factors(b))))                
 ?                      tPb        if len(prime_factors(b)) != 1 else               
                           b           b                                            

Jika ^(1)tidak diizinkan, saya harus menggunakan 33 byte:

L?j\xm+ed?+"^("+yhd\)thdkrPb8tPbb
Tyilo
sumber
4

Mathematica, 106 102 101 - 50 = 51 byte

If[PrimeQ@#,#,(a=CenterDot)@@{b,c}~Function~If[c<2,b,b~Superscript~#0@c]@@@FactorInteger@#/.a@b_:>b]&

Format sebagai eksponen bersarang dengan multiplikasi titik. Representasi Unicode contoh input dan output:

  • 102 · 5
  • 1202³ · 3 · 5
  • 163842²˙⁷
LegionMammal978
sumber
Penggunaan yang bagus CenterDotuntuk menghindari Times. Saya masih mencoba mencari tahu di mana rekursi terjadi.
DavidC
@DavidCarraher #0mengacu pada fungsi murni terdalam tanpa nama argumen.
LegionMammal978
Terima kasih. Pertama kali saya mendengar tentang penggunaan ini#
DavidC
3

Bash + coreutils + bsdgames, 117 - 50 = 67

f()(factor $1|tr \  \\n|sed 1d|uniq -c|while read e m;do
((e>1))&&m+=^{`f $e`}
printf {$m}
done)
f $1|sed s/}{/}\*{/g

Keluaran

$ ./recprimefac.sh 2985984
{2^{{2^{{2}}}*{3}}}*{3^{{2}*{3}}} $ 
$ 

Saya mengklaim bonus -50, karena output ini diformat LaTeX dan dengan alat seperti http://www.sciweavers.org/free-online-latex-equation-editor menjadikan:

masukkan deskripsi gambar di sini

Beri tahu saya jika ini tidak dapat diterima.

Trauma Digital
sumber
1
Itu bekerja dengan baik.
SuperJedi224
1

Klip , 36 33

jm[z.y(z?()z{'^'(M)z')`]L]}qfnx"*

Penjelasan

                            qfnx   .- Prime factors of the input, with exponents -.
  m[z                      }       .- For each factor z...               -.
     .y(z                          .- The prime number                   -.
         ?()z            L]        .- If the exponent is 1, nothing      -.
             {         `]          .- Otherwise, the following:          -.
                  M)z              .- Apply the main function to the exponent... -.
              '^'(   ')            .- ...inside ^(..)                    -.
 j                              "* .- Join the factors with "*"          -.
Ypnypn
sumber
1

Javascript, 388-50 = 338

l="length";function g(n){for(;m(++n););p.push(n)}function m(n){for(i=0;i<p[l];i++)if(n%p[i]==0)return 1;return 0}function f(n,x,q,o){while(p[p[l]-1]<n)g(2);if(p.indexOf(n)>=0||n==1)return n;q=[];while(q[l]<=n)q.push(0);for(i=0;i<p[l];i++){x=p[i];while(n%x==0){q[x]++;n/=x}}o="";for(i=2;i<q[l];i++)if(q[i]){if(o)o+="*";o+=i;if(q[i]>1){o+="^{"+f(q[i])+"}"}}return o}alert(f(+prompt(p=[2])))

Karena kode LaTeX sekarang memenuhi syarat untuk bonus, saya memutuskan untuk memasukkan modifikasi yang diperlukan sebagai bagian dari golf untuk ini. Mungkin masih bisa bermain golf lebih lanjut.

SuperJedi224
sumber