Sebuah pembagi yang tepat adalah pembagi dari sejumlah n , yang tidak n sendiri. Sebagai contoh, pembagi yang tepat dari 12 adalah 1, 2, 3, 4 dan 6.
Anda akan diberikan bilangan bulat x , x ≥ 2, x ≤ 1000 . Tugas Anda adalah untuk menjumlahkan semua pembagi tertinggi yang tepat dari bilangan bulat dari 2 hingga x (inklusif) (OEIS A280050 ).
Contoh (dengan x = 6
):
Temukan semua bilangan bulat antara 2 dan 6 (inklusif): 2,3,4,5,6.
Dapatkan pembagi yang tepat dari semuanya, dan pilih yang tertinggi dari setiap nomor:
- 2 -> 1
- 3 -> 1
- 4 -> 1, 2
- 5 -> 1
- 6 -> 1, 2, 3 .
Jumlah pembagi yang tepat tertinggi:
1 + 1 + 2 + 1 + 3 = 8
.Hasil akhirnya adalah 8.
Uji Kasus
Masukan | Keluaran ------- + --------- | 2 | 1 4 | 4 6 | 8 8 | 13 15 | 41 37 | 229 100 | 1690 1000 | 165279
Aturan
Berlaku celah default .
Anda dapat mengambil input dan memberikan output dengan metode standar apa pun .
Ini adalah kode-golf , pengiriman terpendek yang valid dalam setiap bahasa menang! Selamat bersenang-senang!
Jawaban:
Oasis , 4 byte
Kode:
Cobalah online!
Penjelasan:
Versi diperpanjang:
sumber
Sekam , 7 byte
Cobalah online!
Penjelasan
Husk tidak memiliki built-in untuk menghitung pembagi secara langsung (belum), jadi saya menggunakan faktorisasi utama sebagai gantinya. Pembagi nomor yang tepat terbesar adalah produk dari faktor prima kecuali yang terkecil. Saya memetakan fungsi ini pada rentang dari 2 hingga input, dan menjumlahkan hasilnya.
sumber
Python 2 , 50 byte
Ini lambat dan bahkan tidak bisa mengatasi input 15 pada TIO.
Cobalah online!
Namun, memoisasi ( terima kasih @ musicman523 ) dapat digunakan untuk memverifikasi semua kasus uji.
Cobalah online!
Versi alternatif, 52 byte
Dengan biaya 2 byte, kita dapat memilih apakah akan menghitung
f(n,k+1)
ataun/k+f(n-1)
.Dengan beberapa tipu daya, ini berfungsi untuk semua kasus uji, bahkan pada TIO.
Cobalah online!
sumber
f
ini adalah fungsi murni , Anda dapat memoise untuk menjalankan kasing yang lebih besar di TIOJelly , 6 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Brachylog , 10 byte
Cobalah online!
sumber
JavaScript (ES6), 40 byte
Angka sama dengan produk pembagi tertinggi yang tepat dan faktor prima terkecilnya.
sumber
n>352
(setidaknya dalam cuplikan ini, tidak tahu apakah ini ketergantungan browser / mesin saya) sementara Anda seharusnya mendukung setidaknya upton=1000
.n=1000
jika Anda menggunakan misnode --stack_size=8000
.05AB1E ,
98 byte-1 Byte berkat trik faktor utama Leaky Nun dalam jawaban Pyth-nya
Cobalah online!
Penjelasan
Alternatif 8 Byte solusi (Itu tidak bekerja pada TIO)
dan ofc alternatif solusi 9 Byte (Itu bekerja pada TIO)
sumber
Retina ,
3124 byte7 byte berkat Martin Ender.
Cobalah online!
Bagaimana itu bekerja
Regex
/^(1+)\1+$/
menangkap pembagi terbesar yang tepat dari jumlah tertentu diwakili dalam unary. Dalam kode tersebut,\1+
ini diubah menjadi sintaks lookahead.sumber
Mathematica, 30 byte
sumber
Pyth ,
1398 byte1 byte berkat jacoblaw.
Suite uji .
Bagaimana itu bekerja
Pembagi yang tepat terbesar adalah produk dari faktor prima kecuali yang terkecil.
sumber
Python 2 (PyPy) ,
737170 byteBukan jawaban Python terpendek, tetapi ini hanya angin sepoi-sepoi melalui uji kasus. TIO menangani input hingga 30.000.000 tanpa berkeringat; komputer desktop saya menangani 300.000.000 dalam satu menit.
Dengan biaya 2 byte , kondisi ini
n>d
dapat digunakan untuk peningkatan kecepatan ~ 10%.Terima kasih kepada @xnor untuk
r=[0]*n
idenya, yang menghemat 3 byte!Cobalah online!
sumber
l=[0]*n
harus memungkinkan Anda untuk menyingkirkan-2
.exec
Agak membunuh kecepatan, tetapi bahkan satuwhile
loop akan lebih pendek dari pendekatan saya.Haskell,
484643 byteCobalah online!
Sunting: @rogaos menyimpan dua byte. Terima kasih!
Edit II: ... dan @xnor 3 byte lainnya.
sumber
f 2=1 f n=last[d|d<-[1..n-1],mod n d<1]+f(n-1)
sum
, jadi saya pikir itu tidak lebih pendek.until
menghemat lebih banyak:until((<1).mod n)pred(n-1)+f(n-1)
Japt ,
8 + 2 = 1086 byteMenguji
Penjelasan
sumber
-x
dihitung sebagai dua byte menurut pos ini . Namun, saya pikir Anda dapat menyimpan byte denganò2_â1 o
(â
tidak termasuk nomor asli ketika diberi argumen)â
argumen membuat saya menghemat yang saya cari.õ Å
sebelum dan menemukan beberapa 8- dan 9-byters:õ Åx_/k g
,õ Åx_k Å×
,õ Åx_â¬o
. Dan dengan menggabungkanõ
danÅ
denganxo
trik jenius Anda, saya menemukan solusi 7-byte :-)MATL, 12 byte
Cobalah di MATL Online
Penjelasan
sumber
PHP , 56 byte
Cobalah online!
sumber
Prolog (SWI) , 72 byte
Cobalah online!
sumber
Cubix , 27
39byteCobalah online!
Kubus
Tonton Jalankan
0IU
Siapkan tumpukan dengan akumulator, dan integer awal. Putar balik ke lingkaran luar:(?
duplikat bagian atas tumpukan, penurunan, dan uji\pO@
jika nol lingkaran di sekitar kubus ke cermin, ambil bagian bawah tumpukan, keluaran dan hentikan%\!
jika positif, mod, relect dan tes.u;.W
jika benar, putar balik, hapus hasil mod dan jalur ganti kembali ke loop dalamU;p+qu;;\(
jika falsey, putar u, hapus hasil mod, bawa akumulator ke atas, tambahkan push pembagi integer (atas) ke bawah dan putar u. Bersihkan tumpukan hanya dengan akumulator dan integer saat ini, kurangi integer dan masukkan loop luar lagi.sumber
C # (.NET Core) ,
7472 byteCobalah online!
sumber
break
kej=0
.Sebenarnya , 12 byte
Cobalah online!
sumber
Python 3 ,
78 75 7371 byteBahkan tidak dekat dengan jawaban python Leaky nun dalam hitungan byte.
Cobalah online!
sumber
Python 3 ,
696359 byte4 byte berkat Dennis.
Cobalah online!
Saya menetapkan batas rekursi menjadi 2000 agar ini berfungsi untuk 1000.
sumber
Arang , 37 byte
Cobalah online!
Tautan ke versi verbose. Hampir sepanjang hari saya mencari tahu bagaimana saya bisa menyelesaikan pertanyaan yang tidak terkait dengan seni ASCII di Charcoal, tetapi akhirnya saya mendapatkannya dan saya sangat bangga pada saya. :-D
Ya, saya yakin ini bisa banyak bermain golf. Saya baru saja menerjemahkan jawaban C # saya dan saya yakin semuanya dapat dilakukan secara berbeda di Charcoal. Setidaknya itu menyelesaikan
1000
kasus dalam beberapa detik ...sumber
Pari / GP ,
3630 byteCobalah online!
sumber
Python 2 (PyPy) , 145 byte
Karena mengubah kompetisi kode-golf menjadi kompetisi kode tercepat itu menyenangkan, inilah algoritma O ( n ) yang, pada TIO, memecahkan n = 5.000.000.000 dalam 30 detik. ( Saringan Dennis adalah O ( n log n ).)
Cobalah online!
Bagaimana itu bekerja
Kami menghitung ukuran set
S = {( a , b ) | 2 ≤ a ≤ n , 2 ≤ b ≤ terbesar-benar-pembagi ( a )},
dengan menulis ulang sebagai serikat pekerja, atas semua bilangan prima p ≤ √n, dari
S p = {( p ⋅ d , b ) | 2 ≤ d ≤ n / p , 2 ≤ b ≤ d },
dan menggunakan prinsip inklusi-pengecualian :
| S | = ∑ (−1) m - 1 | S p 1 ∩ ⋯ ∩ S p m | lebih dari m ≥ 1 dan bilangan prima p 1 <⋯ < p m ≤ √n,
dimana
S p 1 ∩ ⋯ ∩ S p m = {( p 1 ⋯ p m ⋅ e , b ) | 1 ≤ e ≤ n / ( p 1 ⋯ p m ), 2 ≤ b ≤ p 1 ⋯ p m - 1 e },
| S p 1 ∩ ⋯ ∩ S p m | = ⌊ n / ( p 1 ⋯ p m ) ⌋⋅ ( p 1 ⋯p m - 1 ⋅ (⌊ n / ( p 1 ⋯ p m ) ⌋ + 1) - 2) / 2.
Jumlahnya memiliki C ⋅ n istilah nol, di mana C konvergen ke beberapa konstanta yang mungkin 6⋅ (1 - ln 2) / π 2 ≈ 0.186544. Hasil akhirnya adalah | S | + n - 1.
sumber
NewStack , 5 byte
Untungnya, sebenarnya ada built in.
Rinciannya:
Dalam bahasa Inggris yang sebenarnya:
Mari kita jalankan contoh untuk input 8.
Nᵢ
: Buat daftar bilangan asli dari 1 hingga 8:1, 2, 3, 4, 5, 6, 7, 8
;
: Hitung faktor terbesar:1, 1, 1, 2, 1, 3, 1, 4
q
. Hapus elemen pertama:1, 1, 2, 1, 3, 1, 4
Σ
Dan ambil jumlahnya:1+1+2+1+3+1+4
=13
sumber
1+1+2+1+3+1+4
=13
tidak8
. Terlepas dari itu: jawaban yang bagus jadi +1.Java 8,
787472 bytePort dari jawaban C # @CarlosAlejo .
Coba di sini.
Jawaban lama (78 byte):
Coba di sini.
Penjelasan (dari jawaban lama):
sumber
Lua , 74 byte
Cobalah online!
sumber
J , 18 byte
Cobalah online!
sumber
Ditumpuk , 31 byte
Cobalah online! (Semua testcases kecuali 1000, yang melebihi batas waktu online 60 detik.)
Penjelasan
sumber
C (gcc) , 53 byte
Cobalah online!
Nyaman dan cepat melewati semua kasus uji.
sumber