Memasukkan

Bilangan bulat tunggal $1 \leq x \leq 10^{15}$ .

Keluaran

Jumlah maksimum bilangan bulat positif berbeda yang memiliki produk $x$ .

Contohnya

Input: 1099511627776. Keluaran: 9. Satu kemungkinan daftar faktor optimal adalah: (1, 2, 4, 8, 16, 32, 64, 128, 4096).

Input: 127381. Output 4. Salah satu daftar faktor optimal yang mungkin adalah: (1, 17, 59, 127).

Terkait dengan pertanyaan lama ini .

code-golf math Anush
sumber

9

Bisakah Anda menambahkan beberapa test case lagi? (Lebih disukai dari ukuran yang wajar.)

Arnauld

8

Diberikan komentar Anda pada sebagian besar jawaban: jika Anda mencari kode efisien, ini seharusnya tidak ditandai sebagai code-golf. Anda dapat mempertimbangkan salah satu fastest-codeatau fastest-algorithmuntuk tantangan yang akan datang. Jika Anda benar-benar ingin semua jawaban berfungsi dalam waktu terbatas dalam rentang yang ditentukan, seharusnya jawaban itu disebutkan secara eksplisit. (Dan saya akan merekomendasikan kisaran yang lebih kecil sehingga tidak bertentangan dengan code-golfsepenuhnya.)

Arnauld

@Arnauld Tidak. Saya berhati-hati untuk membuatnya kode-golf dan tidak ada yang dihakimi untuk itu. Akan lebih keren jika kode bisa berjalan untuk rentang input yang ditentukan.

Anush

5

Mengutip xnor: Jika tidak wajib, jawaban tidak akan melakukannya .

Arnauld

1

Karena x=1, 2, ...saya mendapatkan f(x)=1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 3, 4, 2, 3yang tidak saya temukan di OEIS. Cukup jelas bahwa catatan akan muncul untuk nomor faktorial x. Misalnya yang terkecil xyang f(x)=13akan 13!. Saya kira fhanya bergantung pada eksponen faktorisasi utama. Jadi untuk menemukan f(13^4*19^7*29^2)kita mungkin menyederhanakannya f(2^7*3^4*5^2).

Jeppe Stig Nielsen

5

Bahasa Wolfram (Mathematica) , 52 byte

Max[Length/@Cases[Subsets@Divisors@#,{a__}/;1a==#]]&

Cobalah online!

4-byte disimpan berkat @attinat

Berikut ini juga versi 153 byte yang menghitung 1099511627776dan10^15

Max[Length/@Table[s=RandomSample@Flatten[Table@@@FactorInteger[#]];Last@Select[Times@@@TakeList[s,#]&/@IntegerPartitions@Length@s,DuplicateFreeQ],5!]]+1&

Cobalah online!

Hasilnya 10^15adalah 12

{1, 2, 4, 5, 10, 16, 25, 40, 50, 100, 125, 250}

J42161217
sumber

Tabrakan dengan 1099511627776

Anush

7

@Anush Itu tidak crash. Hanya perlu memori. Anda tidak mengatakan apa-apa tentang keterbatasan memori. Ini adalah kode golf

J42161217

Ya saya sadar. Alangkah baiknya jika Anda benar-benar dapat menjalankan kode rentang input yang ditentukan dalam pertanyaan.

Anush

6

@Anush Ini adalah kode-golf. Bukan jawaban yang bagus. Silakan tentukan kriteria Anda. Jawabannya valid atau tidak. Saya pikir masalahnya di sini adalah pertanyaan ... Mungkin Anda harus mengubahnya ke "algoritma yang paling memadai"

J42161217

3

@Anush Saya membuat edit dalam jawaban saya dan menambahkan satu versi lagi yang sangat cepat dan efisien jika Anda ingin memeriksanya

J42161217

4

Bahasa Wolfram (Mathematica) , 38 byte

(c=n=#;If[i∣n,n/=i,--c]~Do~{i,n};c)&

Cobalah online!

Algoritma serakah. Waktu habis pada TIO pada input yang lebih besar seperti 1099511627776.

attinat
sumber

3

05AB1E , 9 byte

Sangat tidak efisien. Akan kehabisan waktu di TIO untuk angka dengan sejumlah besar pembagi.

ÑæʒPQ}€gZ

Cobalah online!

Penjelasan

Ñ          # push a list of divisors of the input
 æ         # push the powerset of that list
  ʒPQ}     # filter, keep only the lists whose product is the input
      €g   # get the length of each
        Z  # take the maximum

Emigna
sumber

Kode TIO Anda tampaknya menghasilkan 3 bukannya 9.

Anush

@Anush: Ini adalah nomor yang berbeda dari contoh Anda (karena itu berkali-kali karena banyak faktor). Saya mungkin harus menggunakan contoh yang lebih berbeda.

Emigna

€gZsedikit lebih efisien daripada éθgbytecount yang sama.

Grimmy

@ Grimy: Benar. Tidak akan ada banyak perbedaan karena itu adalah filter yang merupakan penjahat besar di sini, tetapi tidak ada salahnya menjadi sedikit lebih efisien :)

Emigna

2

Perl 6 , 38 byte

{$!=$_;+grep {$!%%$_&&($!/=$_)},1..$_}

Cobalah online!

Mengambil pendekatan serakah untuk memilih pembagi.

Jo King
sumber

Tidak berakhir dengan 1099511627776

Anush

6

@ Anush Yah, akhirnya berakhir . Umumnya, jawabannya valid jika algoritma program akan bekerja dengan input apa pun, jika diberikan memori dan waktu sebanyak yang diinginkan. Karena ini adalah kode-golf , saya mengoptimalkannya untuk panjang kode, bukan kompleksitas algoritmik

Jo King

2

Javascript (ES6), 39 byte

f=(n,i=0)=>n%++i?n>i&&f(n,i):1+f(n/i,i)

Mungkin ada beberapa byte yang bisa disimpan di sana-sini. Gunakan saja algoritma serakah untuk faktor-faktornya.

vrugtehagel
sumber

2

Jelly , 9 byte

ŒPP=³ƊƇẈṀ

Cobalah online!

-1 byte terima kasih kepada seseorang

-2 byte terima kasih kepada ErikTheOutgolfer

HyperNeutrino
sumber

Sambil menyiapkan input untuk superseeker OEIS, saya membuat program Jelly kemungkinan golf 11 byte (yang menggunakan pendekatan yang berbeda), dan saya tidak mungkin mengirim jawaban Jelly jadi saya akan berpura-pura saya golf byte dari solusi Anda: ÆE×8‘½’:2S‘(itu bekerja dengan kekuatan bagian "formula" OEIS untuk A003056). Penafian: itu mungkin salah, tetapi bekerja pada kasus uji.

kata ganti saya adalah monicareinstate

Tampaknya tidak berakhir dengan 1099511627776

Anush

@ seseorang tidak bekerja selama 36 tetapi terima kasih

HyperNeutrino

@Anush ya, ini sangat lambat karena saya kode-golf itu, tidak dioptimalkan untuk efisiensi

HyperNeutrino

1

Anda dapat menghapus ÆD, itu tidak seperti ada lebih banyak partisi yang akan dibuat seperti ini, itu hanya akan mengambil lebih banyak waktu (waktu untuk

x \geq 21

$x\ge21$ ).

Erik the Outgolfer

2

Japt `-h` , 13 byte

â à f_×¶UÃmÊn

Cobalah

Perwujudan Ketidaktahuan
sumber

2

Brachylog , 8 byte

f;?⟨⊇×⟩l

Cobalah online!

(Pendekatan naif {~×≠l}ᶠ⌉,, menghasilkan sejumlah solusi tanpa batas dengan tambahan 1s sebelum dihilangkan dengan≠ , dan dengan demikian gagal untuk benar-benar berakhir. Namun, itu bukan masalah, karena itu untuk jumlah byte yang sama!)

Mengambil input melalui variabel input dan output melalui variabel output. Header di TIO berisi salinan sebagian besar kode demi menunjukkan kepada Anda apa daftar faktornya, tetapi ini berfungsi dengan baik tanpa itu. Karena ⊇memberikan sublists yang lebih besar terlebih dahulu, predikat ini pada dasarnya melakukan hal yang sama dengan sebagian besar jawaban lainnya, tetapi tanpa secara eksplisit menghasilkan dan memfilter set lengkap faktor, berkat backtracking.

            The output
       l    is the length of
    ⊇       a sublist (the largest satisfying these constraints)
f           of the factors of
            the input
 ; ⟨  ⟩     which
     ×      with its elements multiplied together
  ?         is the input.

String yang tidak terkait
sumber

1

Scala , 77 byte

def f(n:Long)={var(m,c,i)=(n,1,2L);while(i<=m){if(m%i==0){m/=i;c+=1};i+=1};c}

Cobalah online!

Peter
sumber

1

Gaia , 10 9 byte

Π=
dz↑⁇(l

Cobalah online!

Mengikuti "algoritme" yang sama seperti yang terlihat di tempat lain - saring pembagi powerset paling lama dengan produk yang sama dengan jumlahnya dan kembalikan panjangnya.

	| helper function
Π=	| is prod(list)==n (implicit)?
	|
	| main function; implicitly takes n
dz	| divisor powerset (in decreasing order of size)
  ↑⁇	| filter by helper function
    (l	| take the first element and take the length (implicitly output)

Giuseppe
sumber

0

Clam , 15 byte

p}_`nq#:;qQ@s~Q

TIO link segera hadir (ketika dennis menarik)

Pada dasarnya port dari solusi 05AB1E @ Emigna.

Penjelasan

                - Implicit Q = first input
p               - Print...
 }              - The last element of...
  _             - Sorted...
   `nq          - Lengths of... (map q => q.len)
           @s   - Items in powerset of
             ~Q - Proper divisors of Q
      #         - Where... (filter)
        ;q      - Product of subset
       :        - Equals...
          Q     - Q

Skidsdev
sumber

0

C # (Visual C # Interactive Compiler) , 54 byte

int f(int n,int i=0)=>n%++i<1?1+f(n/i,i):n>i?f(n,i):0;

Menggunakan pendekatan yang sama dengan jawaban @ vrugtehagel dan @ JoKing.

Cobalah online!

Perwujudan Ketidaktahuan
sumber

Dengan asumsi saya menerapkan logika Anda dengan benar, solusi 53-byte (yang saya tidak bisa hilangkan dari kata kunci "kembali"): Coba online!

kata ganti saya adalah monicareinstate

1

@ seseorang Terima kasih, tetapi menurut meta, fungsi harus dapat digunakan kembali . Juga, saya tidak tahu apakah dapat diterima memiliki deklarasi di luar fungsi meninggalkan tanda titik koma, dapat membuat posting meta tentang itu.

Perwujudan Ketidaktahuan

0

Ruby , 34 byte

Jelas sekali ada angka yang sangat besar, tetapi pada akhirnya akan habis jika diberikan waktu yang cukup pada mesin lain.

->n{(1..n).count{|e|n%e<1?n/=e:p}}

Cobalah online!

Nilai Tinta
sumber

Sebuah permainan faktorisasi

Memasukkan

Keluaran

Contohnya

Jawaban:

Bahasa Wolfram (Mathematica) , 52 byte

Bahasa Wolfram (Mathematica) , 38 byte

05AB1E , 9 byte

Perl 6 , 38 byte

Javascript (ES6), 39 byte

Jelly , 9 byte

Japt `-h` , 13 byte

Brachylog , 8 byte

Scala , 77 byte

Gaia , 10 9 byte

Clam , 15 byte

Penjelasan

C # (Visual C # Interactive Compiler) , 54 byte

Ruby , 34 byte

Sebuah permainan faktorisasi

Memasukkan

Keluaran

Contohnya

Jawaban:

Bahasa Wolfram (Mathematica) , 52 byte

Bahasa Wolfram (Mathematica) , 38 byte

05AB1E , 9 byte

Perl 6 , 38 byte

Javascript (ES6), 39 byte

Jelly , 9 byte

Japt -h , 13 byte

Brachylog , 8 byte

Scala , 77 byte

Gaia , 10 9 byte

Clam , 15 byte

Penjelasan

C # (Visual C # Interactive Compiler) , 54 byte

Ruby , 34 byte

Japt `-h` , 13 byte