Ein richtiger Teiler ist ein Teiler einer Zahl n , die nicht n selbst ist. Die richtigen Teiler von 12 sind beispielsweise 1, 2, 3, 4 und 6.

Sie erhalten eine ganze Zahl x , x ≥ 2, x ≤ 1000 . Ihre Aufgabe ist es, alle höchsten richtigen Teiler der ganzen Zahlen von 2 bis x (einschließlich) zu summieren (OEIS A280050 ).

Beispiel (mit x = 6):

• Finden Sie alle ganzen Zahlen zwischen 2 und 6 (einschließlich): 2,3,4,5,6.

• Holen Sie sich die richtigen Teiler von allen und wählen Sie aus jeder Zahl die höchsten aus:

  • 2 -> 1
  • 3 -> 1
  • 4 -> 1, 2
  • 5 -> 1
  • 6 -> 1, 2, 3 .

• Addieren Sie die höchsten richtigen Divisoren: 1 + 1 + 2 + 1 + 3 = 8.

• Das Endergebnis ist 8.

Testfälle

Eingabe | Ausgabe
------- + ---------
       |
 2 | 1
 4 | 4
 6 | 8
 8 | 13
 15 | 41
 37 | 229
 100 | 1690
 1000 | 165279

Regeln

• Es gelten Standardlücken .

• Sie können die Eingabe und Ausgabe nach einer beliebigen Standardmethode vornehmen .

• Dies ist Code-Golf , die kürzeste gültige Einsendung in jeder Sprache gewinnt! Habe Spaß!

Oase , 4 Bytes

Code:

nj+U

Probieren Sie es online!

Erläuterung:

Erweiterte Version:

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)

Schale , 7 Bytes

ṁȯΠtptḣ

Probieren Sie es online!

Erläuterung

Husk verfügt (noch) nicht über eine integrierte Funktion zur direkten Berechnung der Divisoren, daher verwende ich stattdessen die Primfaktor-Faktorisierung. Der größte richtige Teiler einer Zahl ist das Produkt seiner Primfaktoren mit Ausnahme des kleinsten. Ich ordne diese Funktion über den Bereich von 2 bis zur Eingabe zu und summiere die Ergebnisse.

ṁȯΠ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.

Python 2 , 50 Bytes

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

Dies ist langsam und kann nicht einmal Eingang 15 von TIO bewältigen .

Probieren Sie es online!

Mit Memoization ( danke @ musicman523 ) können jedoch alle Testfälle überprüft werden.

Probieren Sie es online!

Alternative Version, 52 Byte

Auf Kosten von 2 Bytes können wir wählen, ob wir berechnen f(n,k+1)oder 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))

Mit einigem Aufwand funktioniert dies für alle Testfälle, sogar für TIO.

Probieren Sie es online!

Gelee , 6 Bytes

ÆḌ€Ṫ€S

Probieren Sie es online!

Wie es funktioniert

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

Brachylog , 10 Bytes

⟦bb{fkt}ᵐ+

Probieren Sie es online!

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>

Eine Zahl entspricht dem Produkt seines höchsten richtigen Divisors und seines kleinsten Primfaktors.

05AB1E , 9 8 Bytes

-1 Byte dank Leaky Nuns Primfaktor-Trick in seiner Pyth-Antwort

L¦vyÒ¦PO

Probieren Sie es online!

Erläuterung

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

Alternative 8-Byte-Lösung (Funktioniert bei TIO nicht)

L¦vyѨθO    

und einer alternativen 9-Byte-Lösung (das funktioniert mit TIO)

L¦vyѨ®èO    

Retina , 31 24 Bytes

7 Bytes dank Martin Ender.

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

Probieren Sie es online!

Wie es funktioniert

Der reguläre Ausdruck /^(1+)\1+$/erfasst den größten richtigen Teiler einer bestimmten Anzahl, die in unary dargestellt ist. Im Code wird die \1+Lookahead-Syntax verwendet.

Mathematica, 30 Bytes

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

Pyth , 13 9 8 Bytes

1 byte dank jacoblaw.

tsm*FtPh

Testsuite .

Wie es funktioniert

Der größte richtige Teiler ist das Produkt der Primfaktoren mit Ausnahme des kleinsten.

Python 2 (PyPy) , 73 71 70 Bytes

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

Nicht die kürzeste Antwort von Python, aber dies ist ein Kinderspiel in den Testfällen. TIO verarbeitet Eingaben bis zu 30.000.000, ohne ins Schwitzen zu geraten . Mein Desktop-Computer verarbeitet 300.000.000 in einer Minute.

Auf Kosten von 2 Bytesn>d könnte die Bedingung für eine Beschleunigung von ~ 10% verwendet werden.

Danke an @xnor für die r=[0]*nIdee, die 3 Bytes gespart hat!

Probieren Sie es online!

Haskell, 48 46 43 Bytes

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

Probieren Sie es online!

Edit: @rogaos sparte zwei Bytes. Vielen Dank!

Edit II: ... und @nicht weitere 3 Bytes.

Japt , 8 + 2 = 10 8 6 Bytes

òâ1 xo

Probier es aus

• Dank ETHproductions 1 Byte gespart.

Erläuterung

    :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

MATL, 12 Bytes

q:Q"@Z\l_)vs

Probieren Sie es bei MATL Online aus

Erläuterung

        % 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

PHP , 56 Bytes

for($i=1;$v||$argn>=$v=++$i;)$i%--$v?:$v=!$s+=$v;echo$s;

Probieren Sie es online!

Prolog (SWI) , 72 Bytes

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.

Probieren Sie es online!

Cubix , 27 39 Bytes

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

Probieren Sie es online!

Cubified

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

Beobachten Sie es laufen

• 0IURichten Sie den Stapel mit einem Akkumulator und der Start-Ganzzahl ein. Wende dich in die äußere Schleife
• :(? Dupliziere die aktuelle Spitze des Stapels, dekrementiere und teste
• \pO@ Wenn der Würfel durch eine Nullschleife zu einem Spiegel geführt wird, greifen Sie nach dem Boden des Stapels, geben Sie ihn aus und halten Sie ihn an
• %\! wenn positiv, mod, relect und test.
  • u;.W wenn es wahr ist, wende dich, entferne das Mod-Ergebnis und wechsle zurück in die innere Schleife
  • U;p+qu;;\(Wenn Sie falsch liegen, wenden Sie, entfernen Sie das Mod-Ergebnis, bringen Sie den Akku nach oben, fügen Sie den aktuellen ganzzahligen (oberen) Divisor hinzu, und drehen Sie. Räumen Sie den Stapel auf, um nur Akkumulator und aktuelle Ganzzahl zu haben, dekrementieren Sie die Ganzzahl und geben Sie die äußere Schleife erneut ein.

C # (.NET Core) , 74 bis 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;}

Probieren Sie es online!

• 2 Bytes rasiert dank Kevin Cruijssen.

Eigentlich 12 Bytes

u2x⌠÷R1@E⌡MΣ

Probieren Sie es online!

Python 3 , 78 75 73 71 Bytes

Nicht einmal annähernd die Python-Antwort von Leaky Nonne in der Byteanzahl.

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

Probieren Sie es online!

Python 3 , 69 63 59 Bytes

4 Bytes dank Dennis.

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

Probieren Sie es online!

Ich habe das Rekursionslimit auf 2000 gesetzt, damit dies für 1000 funktioniert.

Holzkohle , 37 Bytes

Ａ⁰βＦ…·²Ｎ«Ａ⟦⟧δＦ⮌…¹ι«¿¬﹪ικ⊞δκ»Ａ⁺β⌈δβ»Ｉβ

Probieren Sie es online!

Link ist zur ausführlichen Version. Ich habe fast den ganzen Tag gebraucht, um herauszufinden, wie ich eine Frage in Bezug auf Nicht-ASCII-Kunst in Charcoal lösen könnte, aber schließlich habe ich es verstanden und bin sehr stolz auf mich. :-D

Ja, ich bin mir sicher, dass man hier viel Golf spielen kann. Ich habe gerade meine C # -Antwort übersetzt und bin sicher, dass die Dinge in Charcoal anders gemacht werden können. Zumindest löst es den 1000Fall in ein paar Sekunden ...

Pari / GP , 36 30 Bytes

n->sum(i=2,n,i/divisors(i)[2])

Probieren Sie es online!

Python 2 (PyPy) , 145 Bytes

Da es Spaß macht, Codegolfwettbewerbe in Wettbewerbe mit dem schnellsten Code umzuwandeln, gibt es hier einen O ( n ) -Algorithmus, der bei TIO n = 5.000.000.000 in 30 Sekunden löst . ( Dennis Sieb ist 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)

Probieren Sie es online!

Wie es funktioniert

Wir zählen die Größe des Sets

S = {( a , b ) | 2 ≤ a ≤ n , 2 ≤ b ≤ größter Eigenteiler ( a )},

durch Umschreiben als Vereinigung über alle Primzahlen p ≤ √n, von

S _p = {( p ≤ d , b ) | 2 ≤ d ≤ n / p , 2 ≤ b ≤ d },

und unter Verwendung des Einschluss-Ausschluss-Prinzips :

| S | = ∑ (−1) ^{m - 1} | S _{p 1} ≤ ≤ S _{p m} | über m ≥ 1 und Primzahlen p ₁ <⋯ < p _m ≤ √n,

woher

S _{p 1} ∩ ⋯ ∩ S _{p m} = {( p ₁ ≤ p _m ≤ e , b ) | 1 ≤ e ≤ n / ( p ₁ ⋯ p _m ), 2 ≤ b ≤ p ₁ ⋯ p _{m - 1} e },
| S _{p 1} ≤ ≤ S _{p m} | = ≤ n / ( p ₁ ≤ p _m ) ≤ ( p ₁ ≤ p _{m- 1} ≤ (≤ n / ( p ₁ ≤ p _m ) ≤ + 1) - 2) / 2.

Die Summe hat C ⋅ n ungleich Null, wobei C gegen eine Konstante konvergiert, die wahrscheinlich 6 probably (1 - ln 2) / π ² ≈ 0,186544 ist. Das Endergebnis ist dann | S | + n - 1.

NewStack , 5 Bytes

Zum Glück ist tatsächlich eine eingebaut.

Nᵢ;qΣ

Die Panne:

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.

Im eigentlichen Englisch:

Lassen Sie uns ein Beispiel für eine Eingabe von 8 ausführen.

Nᵢ: Liste der natürlichen Zahlen von 1 bis 8 erstellen: 1, 2, 3, 4, 5, 6, 7, 8

;: Berechnen Sie die größten Faktoren: 1, 1, 1, 2, 1, 3, 1, 4

q. Entfernen Sie das erste Element:1, 1, 2, 1, 3, 1, 4

ΣUnd nimm die Summe: 1+1+2+1+3+1+4=13

Java 8, 78 74 72 Bytes

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 von @CarlosAlejos C # Antwort.

Probieren Sie es hier aus.

Alte Antwort (78 Bytes):

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;}

Probieren Sie es hier aus.

Erklärung (der alten Antwort):

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

Lua , 74 Bytes

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)

Probieren Sie es online!

J , 18 Bytes

[:+/1}.&.q:@+}.@i.

Probieren Sie es online!

Gestapelt , 31 Bytes

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

Probieren Sie es online!(Alle Testfälle mit Ausnahme von 1000, bei denen das Online-Zeitlimit von 60 Sekunden überschritten wird.)

Erläuterung

[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

C (gcc) , 53 Bytes

x;s;f(n){for(s=0;n>1;--n){for(x=n;n%--x;);s+=x;}n=s;}

Probieren Sie es online!

Bequem und schnell alle Testfälle bestanden.