Faktorisasi sebagian dari bilangan bulat positif

23

Kumpulan bilangan bulat positif d_1 d_2 ... d_kadalah factorisation dari bilangan bulat positif njika

d_1 * d_2 * ... * d_k = n

Setiap bilangan bulat positif memiliki factorisation prima yang unik , tetapi secara umum mereka juga memiliki factorisation di mana beberapa istilahnya komposit. Misalnya

12 = 6 * 2 = 4 * 3 = 3 * 2 * 2

Tulis sebuah program, fungsi, kata kerja, atau sejenisnya yang mengambil input bilangan bulat positif tunggal dan mengembalikan atau mencetak daftar lengkap dari faktorisasinya yang berbeda. Factorisations dapat diproduksi dalam urutan apa pun, dan ketentuannya mungkin dalam urutan apa pun, tetapi tidak boleh ada dua permutasi satu sama lain. Factorisations mungkin tidak termasuk 1dengan dua pengecualian: untuk input nAnda dapat memberikan factorisation n*1alih-alih n; dan untuk input 1Anda dapat memberikan factorisation 1daripada daftar kosong.

Anda dapat mengasumsikan bahwa input akan berada dalam kisaran integer 32-bit yang ditandatangani. Jika output adalah sebagai string, harus ada perbedaan yang jelas antara penentuan angka dalam faktorisasi dan penetapan faktorisasi, tetapi tidak perlu (misalnya) untuk faktor-faktor untuk digabungkan dengan *.

Kode Anda harus mampu menangani input yang valid dalam waktu 10 menit pada mesin desktop yang masuk akal.

Contohnya

1                  [[]]
                or [[1]]
                or [[1 1]]

7                  [[7]]
                or [[7 1]]
                or [[1 7]]

12                 [[12] [6 2] [4 3] [2 3 2]]
                or variants

16                 [[2 2 2 2] [2 2 4] [2 8] [4 4] [16]]
                or variants

901800900          a list of 198091 factorisations

1338557220         a list of 246218 factorisations
Peter Taylor
sumber
Bisakah Anda memposting daftar factorisations dari 901800900dan di 1338557220suatu tempat di mana kita dapat memeriksanya? Kode saya masing-masing memberi saya faktor 2048 dan 1024 untuk angka-angka itu, dan saya tidak yakin mengapa.
Sherlock9
@ Sherlock9, akan melakukan itu ketika saya pulang. Apa yang bisa saya lakukan dengan generator online adalah memberi Anda output yang valid untuk 5336100 .
Peter Taylor
3
Ini mengingatkan saya pada tantangan ProjectEuler (sayangnya saya tidak ingat yang mana). Tetapi di sana Anda harus menghitung jumlah faktorisasi daripada mendaftarnya.
flawr
OEIS Terkait: A001055
Sherlock9

Jawaban:

12

Haskell, 56 byte

_!1=[[]]
i!n=[j:f|j<-[i..n],mod n j<1,f<-j!div n j]
(2!)

(2!)(1338557220::Int)mencetak dalam lima menit di laptop saya, ketika dikompilasi dengan ghc -O3.

Haskell, 62 byte, tetapi jauh lebih cepat

i!n|i*i>n=[[n]]|0<1=[i:f|mod n i<1,f<-i!div n i]++(i+1)!n
(2!)

(2!)(1338557220::Int)mencetak dalam seperempat detik di laptop saya, ketika dikompilasi dengan ghc -O3.

Anders Kaseorg
sumber
Bagaimana saya menguji ini? ghcberi aku Parse error: naked expression at top leveldan ghciberi akuparse error on input `='
Peter Taylor
@PeterTaylor Ganti fungsi (2!)dengan program main = print ((2!) (1338557220::Int)), kompilasi dengan ghc -O3 factor.hs, dan jalankan dengan ./factor.
Anders Kaseorg
7

Pyth, 29 byte

Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2

M                                def g(G, H):
                   @H2             square root of H
                  S                1-indexed range up to floor
                 >    tG           all but first G − 1 elements
            f                      filter for elements T such that:
              %HT                    H mod T
             !                       is false (0)
   m                               map for elements d:
       gd/Hd                         g(d, H/d)
    +Ld                              prepend d to each element
  a                     ]]H        append [[H]]
 s                                 concatenate
                           g2Q   print g(2, input)

Cobalah online

Berjalan dalam dua puluh detik untuk 1338557220di laptop saya.

Anders Kaseorg
sumber
@PeterTaylor Cara biasa: pyth factor.pyth(atau pyth -c 'Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2'), sediakan 16di stdin. Pastikan Anda menggunakan versi Pyth saat ini; implisit Qditambahkan pada bulan Maret. Saya tidak bisa membayangkan bagaimana Anda bisa mendapatkan pembagian dengan nol.
Anders Kaseorg
Arrrrgh. Saya menggunakan "alih-alih ', dan bash memperluas !%ke sesuatu yang lain.
Peter Taylor
6

Python , 252 313 312 311 145 141 137 135 103 84 83 byte

Ini sebagian besar didasarkan pada jawaban Pyth Anders Kaseorg . Semua saran golf diterima. Cobalah online!

Sunting: 19 byte golf berkat Dennis. Memperbaiki kesalahan ketik dalam kode dan menambahkan tautan TIO.

g=lambda n,m=2:[[n]]+[j+[d]for d in range(m,int(n**.5)+1)if n%d<1for j in g(n/d,d)]

Tidak Disatukan:

def g(n, m=2):
    a = [[n]]
    s = int(n**.5) + 1
    for d in range(m, s):
        if n%d == 0:
            for j in g(n/d, d):
                a.append([d]+j)
    return a
Sherlock9
sumber
1
**.5menghilangkan impor.
Dennis
4

JavaScript (ES6), 83 byte

f=(n,a=[],m=2,i=m)=>{for(;i*i<=n;i++)n%i<1&&f(n/i,[...a,i],i);console.log(...a,n)}

Hanya meminjam trik root kuadrat @ AndersKaseorg karena akhirnya menyelamatkan saya byte secara keseluruhan. Mencetak 1untuk input 1, jika tidak tidak mencetak 1s.

Neil
sumber
1

Ruby 1.9+, 87 89 87 byte

Jawaban ini didasarkan pada jawaban Pyth Anders Kaseorg . Kode ini hanya berfungsi untuk versi setelah Ruby 1.9, karena lambdas yang stabby ->hanya diperkenalkan pada 1.9. Saran bermain golf dipersilakan.

g=->n,m=2{(m..Math.sqrt(n)).select{|i|n%i<1}.flat_map{|d|g[n/d,d].map{|j|[d]+j}}+[[n]]}

Tidak Disatukan:

def g(n, m=2)
  a = [[n]]
  s = (m..Math.sqrt(n))
  t = s.select{|i|n%i<1}
  t.each do |d|
    g[n/d,d].each do |j|
      a.push([d]+j)
    end
  end
  return a
end
Sherlock9
sumber
Apakah ini memerlukan versi Ruby tertentu? Dengan 1.8.7 Saya mendapat keluhan tentang g[n/d,d]:wrong number of arguments (0 for 1)
Peter Taylor
Rupanya lambdas buruk ->diperkenalkan di Ruby 1.9. Saya akan mengedit jawaban untuk menunjukkan nomor versi yang diperlukan.
Sherlock9
Ok terima kasih. Saya masih penasaran g[n/d,d]. g(n/d,d)lebih kompatibel ke belakang.
Peter Taylor
1
Ah, f[n]diperlukan untuk memanggil lambdas stabby dan lambda Ruby secara umum. f(n)dan f npanggilan membutuhkan defdan end. Info lebih lanjut di sini dan di sini
Sherlock9
1

J, 52 byte

[:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:

Tidak seefisien mungkin karena beberapa faktorisasi dapat diulang dan langkah terakhir harus dilakukan setelah mengurutkan masing-masing faktorisasi dan kemudian menduplikasi.

Cobalah online! (Tetapi cobalah untuk menjaga nilai input tetap kecil).

Di desktop saya, waktunya adalah

   f =: [:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:
   timex 'r =: f 1338557220'
3.14172
   # r
246218
   timex 'r =: f 901800900'
16.3849
   # r
198091

Penjelasan

Metode ini bergantung pada menghasilkan semua partisi yang disetel untuk faktor utama bilangan bulat input n . Kinerja terbaik ketika n bebas persegi, jika tidak, faktorisasi duplikat akan dibuat.

[:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:  Input: integer n
                                                  }:  Curtail, forms an empty array
                       q:                             Prime factorization
                     #@                               Length, C = count prime factors
                         _&(                     )    Repeat that many times on x = []
                                 (            )"1       For each row
                                            ~.            Unique
                                         #\@              Enumerate starting at 1
                                       0,                 Prepend 0
                                  ,~"{~                   Append each of those to a
                                                          copy of the row
                               <@                         Box it
                            ;&]                         Set x as the raze of those boxes
                                                      These are now the restricted growth
                                                      strings of order C
    q:                                                Prime factorization
            (    )"$~                                 For each RGS
               /.                                       Partition it
             */                                         Get the product of each block
        /:~@                                            Sort it
      <@                                                Box it
[:~.                                                  Deduplicate
mil
sumber