Znajdź sumę dzielników N

20

Napisz program, który wyświetla na ekranie sumę dzielników liczby (1 ≤ N ≤ 100) wprowadzonych przez użytkownika w zakresie od 1 do N.

To jest OEIS A000203 .

Przykłady:

Wejście : 7

7 / 1 = 7
7 / 7 = 1

7 + 1 = 8

Wyjście: 8

Wejście: 15

15 / 1 = 15
15 / 3 = 5
15 / 5 = 3
15 / 15 = 1

15 + 5 + 3 + 1 = 24

Wyjście: 24

Wejście: 20

20 / 1 = 20
20 / 2 = 10
20 / 4 = 5
20 / 5 = 4
20 / 10 = 2
20 / 20 = 1

20 + 10 + 5 + 4 + 2 + 1 = 42

Wyjście: 42

Wejście: 1

1 / 1 = 1

Wyjście: 1

Wejście: 5

5 / 1 = 5
5 / 5 = 1

5 + 1 = 6

Wyjście: 6

code-golf  sequence  integer  division  factoring 
— Kevin Halley
źródło
6
@ H.PWiz Myślę, że on ma na myśli „dzielniki liczby N”
— benzen
Myślę, że masz na myśli sumę dzielników, czyli funkcję sigma ?
— Stephen
Przepraszam, mam na myśli „Suma wielokrotności N”.
— Kevin Halley,
@ H.PWiz jest to suma tych, więc nie wiem
— Stephen
@ Stephen Wydaje mi się to trywialną zmianą
— H.PWiz

Odpowiedzi:

6

x86-64 Kod maszynowy, 23 bajty

89 F9 89 FE EB 0D 89 F8 99 F7 F1 85 D2 99 0F 44 D1 01 D6 E2 F1 96 C3

Powyższe bajty kodu definiują funkcję, która akceptuje pojedynczą liczbę całkowitą, N, i zwraca w rezultacie sumę jej wielokrotności.

Pojedynczy parametr jest przekazywany w pliku EDI rejestru, zgodny z System V AMD64 ABI (stosowany w systemach * nix). Wynik jest zwracany do EAXrejestru, podobnie jak wszystkie konwencje wywoływania x86.

Algorytm jest bardzo prosty, podobny do wielu innych zgłoszeń w innych językach. Pętlimy N razy, za każdym razem obliczając moduł i dodając go do naszej sumy bieżącej.

Mnemoniki do montażu bez golfa:

; unsigned SumOfMultiples(unsigned N  /* (EDI) */)
    mov     ecx, edi      ; make copy of input N, to be used as our loop counter
    mov     esi, edi      ; make copy of input N, to be used as our accumulator
    jmp     CheckEnd      ; jump directly to 'CheckEnd'
AddModulo:
    mov     eax, edi      ; make copy of input N, to be used as input to DIV instruction
    cdq                   ; short way of setting EDX to 0, based on EAX
    div     ecx           ; divide EDX:EAX by ECX, placing remainder in EDX
    test    edx, edx      ; test remainder, and set ZF if it is zero
    cdq                   ; again, set EDX to 0, without clobbering flags
    cmovz   edx, ecx      ; set EDX to ECX only if remainder was zero (EDX = ZF ? 0 : ECX)
    add     esi, edx      ; add EDX to accumulator
CheckEnd:
    loop    AddModulo     ; decrement loop counter (ECX), and keep looping if it != 0
    xchg    eax, esi      ; move result from accumulator (ESI) into EAX
    ret                   ; return, with result in EAX

Wypróbuj online!

Wydaje się, że powinien istnieć sposób na skrócenie tego, ale nie widzę tego. Obliczenie modulo na x86 wymaga sporo kodu, ponieważ robisz to za pomocą instrukcji DIV(lub IDIV) i oba używają stałych rejestrów wejściowych (EDX i EAX), których wartości są blokowane (ponieważ otrzymują wyniki, reszta i iloraz odpowiednio).

Jedynymi sztuczkami tutaj są dość standardowe gry w golfa:

  • Skonstruowałem kod w nieco nietypowy sposób, dzięki czemu mogę korzystać z LOOPinstrukcji w stylu CISC , która jest po prostu kombinacją DEC+JNZ z ECXrejestrem jako domyślnym operandem.
  • Używam XCHGna końcu zamiastMOV ponieważ ten pierwszy ma specjalne 1-bajtowe kodowanie, gdy EAXjest jednym z operandów.
  • Używam CDQdo wyzerowania EDXw przygotowaniach do podziału, nawet jeśli dla niepodpisanego podziału zwykle zerujesz go za pomocą XOR. Jednak XORzawsze ma 2 bajty, a CDQtylko 1 bajt. Używam CDQponownie po raz drugi w pętli do zera EDX, przed CMOVZinstrukcją. Działa to, ponieważ mogę zagwarantować, że iloraz podziału (in EAX) jest zawsze niepodpisany, więc rozszerzenie znaku na EDXbędzie ustawione EDXna 0.
— Cody Gray
źródło
3

Mathematica, 14 bajtów

Tr@Divisors@#&

lub odpowiedź @Loki

Mathematica, 17 bajtów

DivisorSum[#,#&]&
— J42161217
źródło
@Jennymathy Bardzo miło, dzięki! Równoważny i zabawny sposób na napisanie go to także: DivisorSum [#, # &] &
— Rebel-Scum
@Jennymathy Hmm, jest jeszcze lepiej: Total @ Divisors @ ma tylko 15 znaków! I to działa: np. Total @ Divisors @ 15 daje 24 zgodnie z oczekiwaniami. Mathematica FTW :)
— Rebel-Scum
2
@Loki i Tr@Divisors@#&jeszcze lepiej ;-)
— J42161217
1
@Loki program musi być funkcją, f=która pobiera dane wejściowe f [x], dlatego przedstawiam to w ten sposób. Witamy w PPCG
— J42161217
3
Możesz użyć, Tr@*Divisorsaby ogolić bajt.
— wchargin
3

C, C ++, C #, D, Java, 65 62 bajtów

int d(int n){int s=0,i=1;for(;i<=n;++i)s+=n%i>0?0:i;return s;}

Działa to we wszystkich 5 językach programowania ze względu na podobieństwa.

Optymalizacja C, C ++ i D: 62 60 bajtów

W C ++ i D liczby całkowite są konwertowane niejawnie na logiczne (Zero => false, Not Zero => true), więc nie musisz mieć !=0

int d(int n){int s=0,i=1;for(;i<=n;++i)s+=n%i?0:i;return s;}

Optymalizacja D: system szablonów golfy, 55 bajtów

T d(T)(T n){T s,i=1;for(;i<=n;++i)s+=n%i?0:i;return s;}

Kod do przetestowania :

C:

printf("%d %d %d %d %d", d(7), d(15), d(20), d(1), d(5));

C ++:

std::cout << d(7) << ' ' << d(15) << ' ' << d(20) << ' ' << d(1) << ' ' << d(5);

C #:

class FindSum
{
    int d(int n) { int s = 0, i = 1; for (; i <= n; ++i) s += n % i > 0 ? 0 : i; return s; }

    static void Main(string[] args)
    {
        var f = new FindSum();
        Console.WriteLine(string.Format("{0}, {1}, {2}, {3}, {4}", f.d(7), f.d(15), f.d(20), f.d(1), f.d(5)));
    }
}

D: 

writeln(d(7));
writeln(d(15));
writeln(d(20));
writeln(d(1));
writeln(d(5));

Java:

public class FindSum {
    int d(int n){int s=0,i=1;for(;i<=n;++i)s+=n%i>0?0:i;return s;}

    public static void main(String[] args) {
        FindSum f = new FindSum();
        System.out.println(String.format("%d, %d, %d, %d, %d", f.d(7), f.d(15), f.d(20), f.d(1), f.d(5)));
    }
}
— HatsuPointerKun
źródło
Kilka rzeczy: Po pierwsze, nie sądzę, że potrzebujesz nawiasów wokół n%i/ n%i!=0w dowolnym języku. Po drugie, n%i>0zamiast tego powinno być dostępne Twoje pierwsze rozwiązanie n%i!=0. Po trzecie, rozwiązaniem D może być T d(T)(T n){T s,i=1;for(;i<=n;++i)s+=n%i?0:i;return s;}nadużycie systemu szablonów i wartości domyślnych.
— Zacharý
3

Shnap , 44 43 bajty

-1 do zobaczenia dzięki Panu Xcoderowi (lol zostałem rozegrany w moim własnym języku)

 $n return:{s=0for d:range(n+1)if n%d<1s+=d}

To jest funkcja ($ uruchamia funkcję w Shnap).

Wypróbuj online!

Wyjaśnienie:

$ n                        //Start function with parameter n
    return: {              //Technically, we are returning a scope-block, which evaluates to the last statement run
        s = 0              //Our result
        for d : range(n+1) //For each value in the iterator range(n+1)
            if n % d < 1  // If n is divisible by d
                s += d     // Add d to the sum
                           // Since (s += d) returns (s + d), and a scope-block returns the last run statement, this will be the last statement and equal to our result
    }

Niekonkurencyjne, 19 bajtów

Po wielu aktualizacjach języka można to teraz zredukować do zaledwie 19 bajtów:

$n=>sum(factors(n))

Wypróbuj online!

— Socratic Phoenix
źródło
1
==0to <1( 43 bajty )
— Mr. Xcoder,
@Pan. Dzięki Xcoder ... zostałem rozzłoszczony ... W swoim własnym języku ... Co nawet nie jest ezoteryczne xD
— Socratic Phoenix
2

Python, 44 bajty

lambda k:sum(i*(k%i<1)for i in range(1,1+k))
  • Dzięki Stephen zaoszczędź 1 bajt, usuwając spacje.
  • Dzięki Jonathan Frech zaoszczędź kolejny 1 bajt, zmieniając, czy pomnożyć.
— tsh
źródło
2

J, 23 bajty

[:+/](([:=&0]|[)#])1+i.

Wypróbuj online!

Dla fanów J jest coś sprytne 13-bajtowe rozwiązanie : >:@#.~/.~&.q:ale ponieważ nie był to mój wynalazek, nie publikuję go jako mojej oficjalnej odpowiedzi.

Moje własne rozwiązanie po prostu filtruje 1..n, znajdując dzielniki, a następnie je sumuje. Jego sednem jest widelec widmowy

](([:=&0]|[)#])

Zauważ, że w tym kontekście ]jest to 1..n i [samo jest n. Stąd ]|[są pozostałe przy dzieleniu każdego elementu 1..n na n, i =&0mówi, czy są równe 0.

— Jonasz
źródło
2
To dla 13 bajtów powinno być równoważne:+1#.i.*0=i.|]
— mile
@miles, to naprawdę miłe. Ta część stanowi i.|]wielką poprawę mojego podejścia. Nie do końca jednak rozumiem tę część: +1#.i.- mógłbyś to wyjaśnić?
— Jonasz
2
1#.jest konwersją podstawy 1, która jest równoważna +/"1. Najpierw i.|]zdobądź pozostałe, następnie 0=znajdź te równe 0 (dzielniki), a następnie i.*wyzeruj niepodzielniki w zakresie, następnie zsumuj za pomocą 1#., a następnie dodaj +się, ponieważ i.jest to zakres wyłączny.
— mile
2

JavaScript, 54 44 bajty

n=>[...Array(x=n)].reduce(y=>y+!(n%x)*x--,0)

Zaoszczędź 10 bajtów dzięki Shaggy

Wypróbuj online!

const f = n=>[...Array(x=n)].reduce(y=>y+!(n%x)*x--,0)

console.log(f(7))
console.log(f(15))
console.log(f(20))
console.log(f(1))
console.log(f(5))
Rozwiń fragment kodu

— powelles
źródło
2

Brain-Flak , 96 bajtów

((({})<>){<(([()]{})){<>(({})(<()>))<>{(({})){({}[()])<>}{}}{}<>([{}()]({})){((<{}{}>))}}{}>{}})

Wypróbuj online!

Wyjaśnienie:

Teraz przestarzałe przez ulepszenia.

Sedno algorytmu jest następujące:

({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]({})) turns |N, M...| into |N mod M, M...|
{((<{}{}>))} if the top of stack is not zero, replace it and the second with zero

Jest to modyfikacja mod, która da nam, Mjeśli jest to czynnik Ni 0nie tylko. Pełny kod znajduje się poniżej.

((({})<>) place input, N on both stacks
{ Loop to find factors
 <
  (([()]{})) Decrement and Duplicate; get next factor to check
  { if not zero
   (<>({})<>) Copy N from other stack
   ({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]({})){((<{}{}>))} Code explained above
  }
  {} drop the zero
 >
 {} add the factor
}) push the sum
— MegaTom
źródło
Czy masz wyjaśnienie?
— Wheat Wizard
@FunkyComputerMan Mam już jeden!
— MegaTom,
2

R , 31 26 bajtów

function(N)(x=1:N)%*%!N%%x

Wypróbuj online!

Zwraca 1x1macierz.

Oblicza !N%%xodwzorowuje elementy ddotyczące 1:Npoprzez:d->(1 if d divides N, 0 otherwise)

Następnie x%*%x!N%%xjest iloczyn macierzy, 1:Nktórego wynikiem jest suma xgdzie !N%%xjest 1. Schludny! Technicznie jest to część odpowiedzi Octave Luisa Mendo, ale zobaczyłem to dopiero po tym, jak o tym pomyślałem.

Liczby R +, 14 bajtów

numbers::Sigma

Wypróbuj online!

— Giuseppe
źródło
Dla pierwszego możesz zapisać 2 bajty za pomocą opcjiN=scan();
— gstats
@gstats tak, ale powinienem otrzymać +4 bajty na meta dyskusję . Jeśli masz silną opinię, możesz zastanowić się nad odpowiedzią Jarko, ale ponieważ nikt nie zasugerował alternatywy, przychodzi mi na myśl.
— Giuseppe,
Czy nie powinno być drugie numbers::Sigma(N)? W ten sposób wyświetla kod źródłowy funkcji Sigma.
— Rui Barradas - Przywróć poniedziałek
@RuiBarradas funkcja jest całkowicie dobrym przesłaniem. aby to przetestować, oczywiście musicie to nazwać tak jak ja w pierwszym zgłoszeniu.
— Giuseppe,
1

JavaScript, 31 bajtów

f=(n,i=n)=>i&&!(n%i)*i+f(n,i-1)
— tsh
źródło
1

VBA (Excel), 73 bytes

a=Cells(1,1)
x=1
While x<=a
If a Mod x = 0 Then b=b+x
x=x+1
Wend
MsgBox b
— remoel
źródło
This answer is invalid as it is a collection of snippets that cannot be run as a single unit as stands. To make this valid you will need to convert this to a subroutine or an anonymous VBE immediate window function.
— Taylor Scott
I am not very familiar in what you had said. Can you help me a bit more?
— remoel
To make this post valid you would have to convert it into one of the following formats, 1 - Subroutine, 2 - Function, 3 - Anonymous VBE immediate window function (a single line that can be executed in the Immediate window); For your implementation, the simplest implementation of this would be to convert to a subroutine by wrapping with Sub Y...End Sub to get the 85 Byte solution Sub y A=Cells(1,1) x=1 While x<=A If A Mod x=0 Then b=b+x x=x+1 Wend MsgBox b End Sub
— Taylor Scott
That however can be optimized quite heavily down to the 72 byte solution Sub y While x<=[A1] x=x+1 If [A1]Mod x=0Then b=b+x Wend Debug.?b End Sub which assumes that it is run in a clean module (x = default int value, 0) and outputs to the VBE immediate window (? autoformats to Print )
— Taylor Scott
Beyond this, and recognizing that your solution does not take input via the subroutine call, this can then be converted to a VBE immediate window function for 50 Bytes While x<=[A1]:x=x+1:b=IIf([A1]Mod x,b,b+x):Wend:?b which assumes that x,b are the default value of 0 and outputs to the VBE immediate window (from the VBE immediate window ? is equivalent to Debug.Print )
— Taylor Scott
1

Pyth, 6 bytes

s*M{yP

Try it here!

Pyth doesn't have a built-in for divisors, so I think this is reasonable.

Explanation

s*M{yP    - Full program with implicit input.

     P    - The prime factors of the input.
    y     - The powerset of its prime factors.
   {      - Deduplicate.
 *M       - Map with multiplication.
s         - Sum.
          - Implicitly display the result.

Given 20, for instance, this is what our program does after each instruction:

  • P: [2, 2, 5].

  • y: [[], [2], [2], [5], [2, 2], [2, 5], [2, 5], [2, 2, 5]].

  • {: [[], [2], [5], [2, 2], [2, 5], [2, 2, 5]].

  • *M: [1, 2, 5, 4, 10, 20].

  • s: 42.

— Mr. Xcoder
źródło
1

Husk, 5 bytes

ṁΠuṖp

Try it online!

How?

ṁΠuṖp  - Full program, implicit input.

     p  - Prime factors.
    Ṗ   - Powerset.
   u    - Remove duplicates.
ṁΠ     - Get the product of each list, sum and implicitly output.

Thanks to Zgarb for the suggestions in chat!

— Mr. Xcoder
źródło
0

Bash + GNU utilities, 36

bc<<<`seq -f"n=%g;a+=n*!$1%%n;" $1`a

Try it online.

Pure Bash, 41

for((;++i<=$1;a+=$1%i?0:i))
{
:
}
echo $a

Try it online.

I first tried a fancy bash expansion answer, but it ended up being longer than the simple loop above:

echo $[$(eval echo +\\\(n={1..$1},$1%n?0:n\\\))]
— Digital Trauma
źródło
0

QBIC, 17 bytes

[:|~b%a|\p=p+a}?p

Explanation

[:|      FOR a = 1; a <= b (read from cmd line); a++
~b%a|    IF b modulo a has a remainder THEN - empty block - 
\p=p+a   ELSE add divisor 'a' to running total 'p'
}        END IF, NEXT
?p       PRINT p
— steenbergh
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.