Pembatas yang benar

20

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

Tuan Xcoder
sumber
Bak pasir.
Tn. Xcoder
5
Jika Anda akan memberi sandbox sesuatu, biarkan di sana selama lebih dari dua jam.
Peter Taylor
@PeterTaylor Saya mengirim pesan hanya untuk menerima umpan balik, karena ini adalah tantangan yang sangat sederhana yang biasanya tidak saya posting di kotak pasir sama sekali. Terima kasih BTW untuk hasil editnya.
Tn. Xcoder

Jawaban:

13

Oasis , 4 byte

Kode:

nj+U

Cobalah online!

Penjelasan:

Versi diperpanjang:

nj+00

    0   = a(0)
   0    = a(1)

a(n) =

n       # Push n
 j      # Get the largest divisor under n
  +     # Add to a(n - 1)
Adnan
sumber
5

Sekam , 7 byte

ṁȯΠtptḣ

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.

ṁȯΠtptḣ  Define a function:
      ḣ  Range from 1 to input.
     t   Remove the first element (range from 2).
ṁ        Map over the list and take sum:
 ȯ        The composition of
    p     prime factorization,
   t      tail (remove smallest prime) and
  Π       product.
Zgarb
sumber
5

Python 2 , 50 byte

f=lambda n,k=2:n/k and(f(n,k+1),n/k+f(n-1))[n%k<1]

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)atau n/k+f(n-1).

f=lambda n,k=2:n>1and(n%k and f(n,k+1)or n/k+f(n-1))

Dengan beberapa tipu daya, ini berfungsi untuk semua kasus uji, bahkan pada TIO.

Cobalah online!

Dennis
sumber
Karena fini adalah fungsi murni , Anda dapat memoise untuk menjalankan kasing yang lebih besar di TIO
musicman523
Benar, tidak bisa menggunakan dekorator membuatku marah. Terima kasih!
Dennis
4

Jelly , 6 byte

ÆḌ€Ṫ€S

Cobalah online!

Bagaimana itu bekerja

ÆḌ€Ṫ€S
ÆḌ€    map proper divisor (1 would become empty array)
           implicitly turns argument into 1-indexed range
   Ṫ€  map last element
     S sum
Biarawati Bocor
sumber
4

Brachylog , 10 byte

⟦bb{fkt}ᵐ+

Cobalah online!

Biarawati Bocor
sumber
Anda telah memenangkan ini dengan jelas dalam semua bahasa sejauh ini :))
Mr. Xcoder
4

JavaScript (ES6), 40 byte

f=(n,i=2)=>n<2?0:n%i?f(n,i+1):n/i+f(n-1)
<input type=number oninput=o.textContent=f(this.value)><pre id=o>

Angka sama dengan produk pembagi tertinggi yang tepat dan faktor prima terkecilnya.

Neil
sumber
stack overflows for n>352(setidaknya dalam cuplikan ini, tidak tahu apakah ini ketergantungan browser / mesin saya) sementara Anda seharusnya mendukung setidaknya upto n=1000.
officialaimm
@officialaimm Ini berfungsi n=1000jika Anda menggunakan mis node --stack_size=8000.
Neil
4

05AB1E , 9 8 byte

-1 Byte berkat trik faktor utama Leaky Nun dalam jawaban Pyth-nya

L¦vyÒ¦PO

Cobalah online!

Penjelasan

L¦vyÒ¦PO
L¦       # Range [2 .. input]
  vy     # For each...
    Ò¦    # All prime factors except the first one
      P   # Product
       O  # Sum with previous results
         # Implicit print

Alternatif 8 Byte solusi (Itu tidak bekerja pada TIO)

L¦vyѨθO    

dan ofc alternatif solusi 9 Byte (Itu bekerja pada TIO)

L¦vyѨ®èO    
Datboi
sumber
4

Retina , 31 24 byte

7 byte berkat Martin Ender.

.+
$*
M!&`(1+)(?=\1+$)
1

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.

Biarawati Bocor
sumber
4

Mathematica, 30 byte

Divisors[i][[-2]]~Sum~{i,2,#}&
J42161217
sumber
4

Pyth , 13 9 8 byte

1 byte berkat jacoblaw.

tsm*FtPh

Suite uji .

Bagaimana itu bekerja

Pembagi yang tepat terbesar adalah produk dari faktor prima kecuali yang terkecil.

Biarawati Bocor
sumber
8 byte
jacoblaw
4

Python 2 (PyPy) , 73 71 70 byte

n=input();r=[0]*n;d=1
while n:n-=1;r[d+d::d]=n/d*[d];d+=1
print sum(r)

Bukan 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>ddapat digunakan untuk peningkatan kecepatan ~ 10%.

Terima kasih kepada @xnor untuk r=[0]*nidenya, yang menghemat 3 byte!

Cobalah online!

Dennis
sumber
Lucu, pada dasarnya saya hanya menulis kode yang sama .
xnor
l=[0]*nharus memungkinkan Anda untuk menyingkirkan -2. execAgak membunuh kecepatan, tetapi bahkan satu whileloop akan lebih pendek dari pendekatan saya.
Dennis
Ini sepertinya sedikit lebih cepat daripada pendekatan saya. Keberatan jika saya mengeditnya menjadi jawaban saya?
Dennis
Tolong, pergi untuk itu.
xnor
1
@ Mr.Xcoder Tidak di PyPy, tapi ya, saringan tidak masalah untuk masalah seperti ini.
Dennis
4

Haskell, 48 46 43 byte

f 2=1
f n=until((<1).mod n)pred(n-1)+f(n-1)

Cobalah online!

Sunting: @rogaos menyimpan dua byte. Terima kasih!

Edit II: ... dan @xnor 3 byte lainnya.

nimi
sumber
-2 byte:f 2=1 f n=last[d|d<-[1..n-1],mod n d<1]+f(n-1)
vroomfondel
@rogaos: Terima kasih! Saya sudah mencoba rekursi eksplisit sendiri, tetapi tidak menghapus sum, jadi saya pikir itu tidak lebih pendek.
nimi
1
untilmenghemat lebih banyak:until((<1).mod n)pred(n-1)+f(n-1)
xnor
4

Japt , 8 + 2 = 10 8 6 byte

òâ1 xo

Menguji

  • 1 byte disimpan berkat produk ETH.

Penjelasan

    :Implicit input of integer U.
ò   :Generate an array of integers from 1 to U, inclusive
â   :Get the divisors of each number,
1   :  excluding itself.
x   :Sum the main array
o   :by popping the last element from each sub-array.
    :Implicit output of result
Shaggy
sumber
Perhatikan bahwa -xdihitung sebagai dua byte menurut pos ini . Namun, saya pikir Anda dapat menyimpan byte dengan ò2_â1 o( âtidak termasuk nomor asli ketika diberi argumen)
ETHproduksi
Terima kasih, @ETHproductions; Aku merindukan kedua hal itu. Saya bertanya-tanya apakah itu berlaku surut untuk semua solusi di mana kami menghitung bendera sebagai 1 byte? Saya sedang mencari solusi alternatif yang tidak menggunakan bendera; menunjukkan âargumen membuat saya menghemat yang saya cari.
Shaggy
Saya berasumsi begitu, karena kami tidak benar-benar mengikuti konsensus sebelumnya. BTW, saya telah bermain dengan õ Åsebelum dan menemukan beberapa 8- dan 9-byters: õ Åx_/k g, õ Åx_k Å×, õ Åx_â¬o. Dan dengan menggabungkan õdan Ådengan xotrik jenius Anda, saya menemukan solusi 7-byte :-)
ETHproductions
3

MATL, 12 byte

q:Q"@Z\l_)vs

Cobalah di MATL Online

Penjelasan

        % Implicitly grab input (N)
q       % Subtract one
:       % Create an array [1...(N-1)]
Q       % Add one to create [2...N]
"       % For each element
  @Z\   % Compute the divisors of this element (including itself)
  l_)   % Grab the next to last element (the largest that isn't itself)
  v     % Vertically concatenate the entire stack so far
  s     % Sum the result
Suever
sumber
3

Prolog (SWI) , 72 byte

f(A,B):-A=2,B=1;C is A-1,f(C,D),between(2,A,E),divmod(A,E,S,0),B is D+S.

Cobalah online!

Biarawati Bocor
sumber
3

Cubix , 27 39 byte

?%\(W!:.U0IU(;u;p+qu.@Op\;;

Cobalah online!

Kubus

      ? % \
      ( W !
      : . U
0 I U ( ; u ; p + q u .
@ O p \ ; ; . . . . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

Tonton Jalankan

  • 0IUSiapkan 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 dalam
    • U;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.
MickyT
sumber
3

C # (.NET Core) , 74 72 byte

n=>{int r=0,j;for(;n>1;n--)for(j=n;--j>0;)if(n%j<1){r+=j;j=0;}return r;}

Cobalah online!

  • 2 byte dicukur berkat Kevin Cruijssen.
Charlie
sumber
1
Aku tahu itu sudah sekitar satu tahun, tetapi Anda dapat golf breakke j=0.
Kevin Cruijssen
@KevinCruijssen trik yang sangat sederhana namun efektif. Ide bagus!
Charlie
2

Python 3 , 78 75 73 71 byte

Bahkan tidak dekat dengan jawaban python Leaky nun dalam hitungan byte.

f=lambda z:sum(max(i for i in range(1,y)if 1>y%i)for y in range(2,z+1))

Cobalah online!

officialaimm
sumber
1
Anda semakin dekat dengan revisi pertama jawaban saya ... Anda dapat memeriksa riwayat pengeditan saya.
Leaky Nun
Oh, haha ​​... Aku bersumpah aku tidak mencurinya ... :)
officialaimm
2

Python 3 , 69 63 59 byte

4 byte berkat Dennis.

f=lambda n:n-1and max(j for j in range(1,n)if n%j<1)+f(n-1)

Cobalah online!

Saya menetapkan batas rekursi menjadi 2000 agar ini berfungsi untuk 1000.

Biarawati Bocor
sumber
+1 Anda mendapatkan poin brownies saya! Itulah solusi yang saya bicarakan ketika mengatakan "lebih pendek dari 70 byte" ...
Mr. Xcoder
Juga, ini bekerja di Python 2 juga
Tn. Xcoder
2

Arang , 37 byte

A⁰βF…·²N«A⟦⟧δF⮌…¹ι«¿¬﹪ικ⊞δκ»A⁺β⌈δβ»Iβ

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 1000kasus dalam beberapa detik ...

Charlie
sumber
2

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 ).)

import sympy
n=input()
def g(i,p,k,s):
 while p*max(p,k)<=n:l=k*p;i+=1;p=sympy.sieve[i];s-=g(i,p,l,n/l*(n/l*k+k-2)/2)
 return s
print~g(1,2,1,-n)

Cobalah online!

Bagaimana itu bekerja

Kami menghitung ukuran set

S = {( a , b ) | 2 ≤ an , 2 ≤ b ≤ terbesar-benar-pembagi ( a )},

dengan menulis ulang sebagai serikat pekerja, atas semua bilangan prima p ≤ √n, dari

S p = {( pd , b ) | 2 ≤ dn / p , 2 ≤ bd },

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 1p me , b ) | 1 ≤ en / ( p 1p m ), 2 ≤ bp 1p m - 1 e },
| S p 1 ∩ ⋯ ∩ S p m | = ⌊ n / ( p 1p m ) ⌋⋅ ( p 1p m - 1 ⋅ (⌊ n / ( p 1p m ) ⌋ + 1) - 2) / 2.

Jumlahnya memiliki Cn istilah nol, di mana C konvergen ke beberapa konstanta yang mungkin 6⋅ (1 - ln 2) / π 2 ≈ 0.186544. Hasil akhirnya adalah | S | + n - 1.

Anders Kaseorg
sumber
Oooh, itu cepat ...
Tn. Xcoder
2

NewStack , 5 byte

Untungnya, sebenarnya ada built in.

Nᵢ;qΣ

Rinciannya:

Nᵢ       Add the first (user's input) natural numbers to the stack.
  ;      Perform the highest factor operator on whole stack.
   q     Pop bottom of stack.
    Σ    Sum stack.

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

Graviton
sumber
1+1+2+1+3+1+4= 13tidak 8. Terlepas dari itu: jawaban yang bagus jadi +1.
Kevin Cruijssen
@KevinCruijssen Whoops, terima kasih sudah menangkapnya!
Graviton
2

Java 8, 78 74 72 byte

n->{int r=0,j;for(;n>1;n--)for(j=n;j-->1;)if(n%j<1){r+=j;j=0;}return r;}

Port dari jawaban C # @CarlosAlejo .

Coba di sini.

Jawaban lama (78 byte):

n->{int r=0,i=1,j,k;for(;++i<=n;r+=k)for(j=1,k=1;++j<i;k=i%j<1?j:k);return r;}

Coba di sini.

Penjelasan (dari jawaban lama):

n->{                    // Method with integer parameter and integer return-type
  int r=0,              //  Result-integers
      i=1,j,k;          //  Some temp integers
  for(;++i<=n;          //  Loop (1) from 2 to `n` (inclusive)
      r+=k)             //    And add `k` to the result after every iteration
    for(j=1,k=1;++j<i;  //   Inner loop (2) from `2` to `i` (exclusive)
      k=i%j<1?j:k       //    If `i` is dividable by `j`, replace `k` with `j`
    );                  //   End of inner loop (2)
                        //  End of loop (2) (implicit / single-line body)
  return r;             //  Return result-integer
}                       // End of method
Kevin Cruijssen
sumber
1

Lua , 74 byte

c=0 for i=2,...do for j=1,i-1 do t=i%j<1 and j or t end c=c+t end print(c)

Cobalah online!

Biarawati Bocor
sumber
1

Ditumpuk , 31 byte

[2\|>[divisors:pop\MAX]map sum]

Cobalah online! (Semua testcases kecuali 1000, yang melebihi batas waktu online 60 detik.)

Penjelasan

[2\|>[divisors:pop\MAX]map sum]
 2\|>                               range from 2 to the input inclusive
     [                ]map          map this function over the range
      divisors                      get the divisors of the number (including the number)
              :pop\                 pop a number off the array and swap it with the array
                   MAX              gets the maximum value from the array
                           sum      sum's all the max's
Conor O'Brien
sumber