Kumpulan bilangan bulat positif d_1 d_2 ... d_k
adalah factorisation dari bilangan bulat positif n
jika
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 1
dengan dua pengecualian: untuk input n
Anda dapat memberikan factorisation n*1
alih-alih n
; dan untuk input 1
Anda dapat memberikan factorisation 1
daripada 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
sumber
901800900
dan di1338557220
suatu 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.Jawaban:
Haskell, 56 byte
(2!)(1338557220::Int)
mencetak dalam lima menit di laptop saya, ketika dikompilasi denganghc -O3
.Haskell, 62 byte, tetapi jauh lebih cepat
(2!)(1338557220::Int)
mencetak dalam seperempat detik di laptop saya, ketika dikompilasi denganghc -O3
.sumber
ghc
beri akuParse error: naked expression at top level
danghci
beri akuparse error on input `='
(2!)
dengan programmain = print ((2!) (1338557220::Int))
, kompilasi denganghc -O3 factor.hs
, dan jalankan dengan./factor
.Pyth, 29 byte
Cobalah online
Berjalan dalam dua puluh detik untuk
1338557220
di laptop saya.sumber
pyth factor.pyth
(ataupyth -c 'Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2'
), sediakan16
di stdin. Pastikan Anda menggunakan versi Pyth saat ini; implisitQ
ditambahkan pada bulan Maret. Saya tidak bisa membayangkan bagaimana Anda bisa mendapatkan pembagian dengan nol."
alih-alih'
, dan bash memperluas!%
ke sesuatu yang lain.Python ,
2523133123111451411371351038483 byteIni 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.
Tidak Disatukan:
sumber
**.5
menghilangkan impor.JavaScript (ES6), 83 byte
Hanya meminjam trik root kuadrat @ AndersKaseorg karena akhirnya menyelamatkan saya byte secara keseluruhan. Mencetak
1
untuk input1
, jika tidak tidak mencetak1
s.sumber
Ruby 1.9+,
878987 byteJawaban 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.Tidak Disatukan:
sumber
g[n/d,d]
:wrong number of arguments (0 for 1)
->
diperkenalkan di Ruby 1.9. Saya akan mengedit jawaban untuk menunjukkan nomor versi yang diperlukan.g[n/d,d]
.g(n/d,d)
lebih kompatibel ke belakang.f[n]
diperlukan untuk memanggil lambdas stabby dan lambda Ruby secara umum.f(n)
danf n
panggilan membutuhkandef
danend
. Info lebih lanjut di sini dan di siniJ, 52 byte
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
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.
sumber