Trouver la somme des diviseurs de N

20

Écrivez un programme qui affiche à l'écran la somme des diviseurs d'un nombre (1 ≤ N ≤ 100) entré par l'utilisateur dans la plage de 1 à N.

Il s'agit d' OEIS A000203 .

Exemples:

Entrée : 7

7 / 1 = 7
7 / 7 = 1

7 + 1 = 8

Sortie: 8

Entrée: 15

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

15 + 5 + 3 + 1 = 24

Sortie: 24

Entrée: 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

Sortie: 42

Entrée: 1

1 / 1 = 1

Sortie: 1

Entrée: 5

5 / 1 = 5
5 / 5 = 1

5 + 1 = 6

Sortie: 6

code-golf sequence integer division factoring Kevin Halley
la source
6
@ H.PWiz Je pense qu'il signifie "les diviseurs d'un nombre N"
benzène
Je pense que vous voulez dire la somme des diviseurs, alias, la fonction sigma ?
Stephen
Désolé, je veux dire "La somme du multiple de N".
Kevin Halley
@ H.PWiz c'est la somme de ceux-là, donc je ne sais pas
Stephen
@Stephen Cela me semble être un changement trivial
H.PWiz

Réponses:

6

Code machine x86-64, 23 octets

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

Les octets de code ci-dessus définissent une fonction qui accepte un seul entier, N, et renvoie la somme de ses multiples en conséquence.

Le paramètre unique est transmis dans le EDIregistre, conformément au système V AMD64 ABI (utilisé sur les systèmes de type * nix). Le résultat est renvoyé dans le EAXregistre, comme avec toutes les conventions d'appel x86.

L'algorithme est très simple, semblable à de nombreuses autres soumissions dans d'autres langues. Nous bouclons N fois, calculant à chaque fois le modulo et l'ajoutant à notre total cumulé.

Mnémoniques d'assemblage non golfés:

; 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

Essayez-le en ligne!

Il semble bien qu'il devrait y avoir un moyen de raccourcir cela, mais je ne le vois pas. Le calcul de modulo sur x86 prend un peu de code, car vous le faites en utilisant l' instruction DIV(ou IDIV), et les deux utilisent des registres d'entrée fixes ( EDXet EAX), dont les valeurs sont bouleversées (car elles reçoivent les résultats, le reste et quotient, respectivement).

Les seuls vrais trucs ici sont des tours de golf assez standard:

  • J'ai structuré le code d'une manière quelque peu inhabituelle afin de pouvoir utiliser l' LOOPinstruction de style CISC , qui est essentiellement une combinaison de DEC+ JNZavec le ECXregistre comme opérande implicite.
  • J'utilise XCHGà la fin au lieu de MOVparce que le premier a un codage spécial à 1 octet quand EAXest l'un des opérandes.
  • J'utilise CDQpour mettre à zéro EDXen préparation de la division, même si pour la division non signée, vous le mettriez normalement à zéro en utilisant a XOR. Cependant, XORest toujours de 2 octets, alors qu'il CDQn'est que de 1 octet. J'utilise à CDQnouveau une deuxième fois à l'intérieur de la boucle à zéro EDX, avant l' CMOVZinstruction. Cela fonctionne parce que je peux être assuré que le quotient de la division (in EAX) est toujours non signé, donc une extension de signe dansEDX sera définie EDXsur 0.
Cody Grey
la source
3

Japt , 3 octets

â)x

Essayez-le en ligne!

powelles
la source
Alternative:â x
M. Xcoder
@ Mr.Xcoder: pas vraiment une alternative; il fait exactement la même chose - la seule différence est le choix de la parenthèse.
Shaggy
Ou avec le drapeau -x, cela pourrait être un octet
Incarnation de l'ignorance
3

Mathematica, 14 octets

Tr@Divisors@#&

ou une réponse de @Loki

Mathematica, 17 octets

DivisorSum[#,#&]&
J42161217
la source
@Jennymathy Très sympa, merci! Une manière équivalente et amusante de l'écrire est aussi: DivisorSum [#, # &] &
Rebel-Scum
@Jennymathy Hmm, c'est encore mieux: Total @ Divisors @ ne fait que 15 caractères! Et cela fonctionne: par exemple, Total @ Divisors @ 15 donne 24 comme prévu. Mathematica FTW :)
Rebel-Scum
2
@Loki et Tr@Divisors@#&encore mieux ;-)
J42161217
1
@Loki le programme doit être une fonction f=qui prend une entrée f [x] c'est pourquoi je le présente de cette façon. Bienvenue sur PPCG
J42161217
3
Vous pouvez utiliser Tr@*Divisorspour raser un octet.
wchargin
3

C, C ++, C #, D, Java, 65 62 octets

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

Cela fonctionne dans toutes ces 5 langages de programmation en raison de similitudes.

Optimisation C, C ++ et D: 62 60 octets

En C ++ et D, les entiers se convertissent implicitement en booléens (Zero => false, Not Zero => true), vous n'avez donc pas besoin d'avoir le !=0

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

Optimisation D: système de modèles golfy, 55 octets

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

Code à tester :

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

RÉ : 

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
la source
Quelques choses: Tout d'abord, je ne pense pas que vous ayez besoin de parenthèses autour du n%i/ n%i!=0dans aucune des langues. Deuxièmement, votre première solution devrait pouvoir avoir n%i>0au lieu de n%i!=0. Troisièmement, la solution de D peut être T d(T)(T n){T s,i=1;for(;i<=n;++i)s+=n%i?0:i;return s;}en abusant du système de modèles et des valeurs par défaut.
Zacharý
3

Shnap , 44 43 octets

-1 bye merci à M. Xcoder (lol j'étais outgolfé dans ma propre langue)

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

Ceci est une fonction ($ démarre une fonction dans Shnap).

Essayez-le en ligne!

Explication:

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

Sans concurrence, 19 octets

Après de nombreuses mises à jour linguistiques, cela peut maintenant être réduit à un maigre 19 octets:

$n=>sum(factors(n))

Essayez-le en ligne!

Phénix socratique
la source
1
==0est <1( 43 octets )
M. Xcoder
@Monsieur. Merci Xcoder ... J'ai été dépassé ... Dans ma propre langue ... Ce qui n'est même pas ésotérique xD
Socratic Phoenix
2

Python, 44 octets

lambda k:sum(i*(k%i<1)for i in range(1,1+k))
  • Grâce à Stephen, économisez 1 octet en supprimant les espaces.
  • Grâce à Jonathan Frech, économisez encore 1 octet en changeant si pour multiplier.
tsh
la source
2

J, 23 octets

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

Essayez-le en ligne!

Pour les fans de J, il existe une solution astucieuse de 13 octets : >:@#.~/.~&.q:mais comme ce n'est pas mon invention, je ne la poste pas comme ma réponse officielle.

Ma propre solution filtre simplement 1..n, trouvant des diviseurs, puis les additionne. Le nœud est la fourche dyadique

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

Notez que dans ce contexte ]est 1..n, et [est n lui-même. D'où ]|[les restes lors de la division de chaque élément de 1..n en n, et =&0vous indique s'ils sont égaux à 0.

Jonas
la source
2
Cela pour 13 octets devrait être équivalent:+1#.i.*0=i.|]
miles
@miles, c'est vraiment sympa. Cette partie est i.|]une grande amélioration de mon approche. Je ne comprends pas bien cette partie: +1#.i.- pourriez-vous l'expliquer?
Jonah
2
1#. est la conversion en base 1, ce qui équivaut à +/"1 . D'abord i.|]pour obtenir les restes, puis 0=pour trouver ceux égaux à 0 (les diviseurs), puis i.*pour mettre à zéro les non-diviseurs dans la plage, puis additionner en utilisant 1#., puis s'ajouter +puisqu'il i.s'agit d'une plage exclusive.
miles
2

Javascript, 54 44 octets

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

10 octets enregistrés grâce à Shaggy

Essayez-le en ligne!

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))
Développer l'extrait

powelles
la source
2

Brain-Flak , 96 octets

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

Essayez-le en ligne!

Explication:

Désormais obsolète par des améliorations.

Le cœur de l'algorithme est le suivant:

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

C'est une modification sur le mod qui nous donnera Msi c'est un facteur de Net 0autrement. Le code complet est ci-dessous.

((({})<>) 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
la source
Avez-vous une explication?
Wheat Wizard
@FunkyComputerMan J'en ai un maintenant!
MegaTom
2

R , 31 26 octets

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

Essayez-le en ligne!

Renvoie une 1x1matrice.

Calcule les !N%%xéléments cartographiques dde 1:Npar:d->(1 if d divides N, 0 otherwise)

Alors, x%*%x!N%%xle produit matriciel 1:Ndonne la somme de xoù !N%%xest 1. Soigné! Techniquement un port de la réponse Octave de Luis Mendo mais je ne l'ai vu qu'après y avoir pensé.

Numéros R +, 14 octets

numbers::Sigma

Essayez-le en ligne!

Giuseppe
la source
Pour le premier, vous pouvez enregistrer 2 octets avecN=scan();
gstats
@gstats oui, mais je devrais obtenir +4 octets par méta-discussion . Si vous avez une forte opinion, vous pouvez peser sur la réponse de Jarko, mais comme personne n'a suggéré d'alternative, cela me vient à l'esprit.
Giuseppe
Le deuxième ne devrait-il pas l'être numbers::Sigma(N)? Comme cela, il génère le code source de la fonction Sigma.
Rui Barradas - Rétablir Monic le
@RuiBarradas a function est une soumission parfaitement bonne. pour le tester, vous devez évidemment l'appeler comme je le fais dans la première soumission.
Giuseppe
1

JavaScript, 31 octets

f=(n,i=n)=>i&&!(n%i)*i+f(n,i-1)
tsh
la source
1

VBA (Excel), 73 octets

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
la source
Cette réponse n'est pas valide car il s'agit d'une collection d'extraits de code qui ne peuvent pas être exécutés comme une seule unité en l'état. Pour le rendre valide, vous devrez le convertir en sous-programme ou en fonction de fenêtre immédiate VBE anonyme.
Taylor Scott
Je ne connais pas très bien ce que vous avez dit. Pouvez-vous m'aider un peu plus?
remoel
Pour rendre ce message valide, vous devez le convertir dans l'un des formats suivants: 1 - Sous-programme, 2 - Fonction, 3 - Fonction de fenêtre immédiate VBE anonyme (une seule ligne qui peut être exécutée dans la fenêtre Exécution); Pour votre implémentation, l'implémentation la plus simple serait de convertir un sous-programme en encapsulant avec Sub Y... End Subpour obtenir la solution de 85 octetsSub 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
Cependant, cela peut être optimisé assez fortement jusqu'à la solution de 72 octets Sub y While x<=[A1] x=x+1 If [A1]Mod x=0Then b=b+x Wend Debug.?b End Subqui suppose qu'il est exécuté dans un module propre (x = valeur int par défaut 0) et sort dans la fenêtre immédiate VBE ( ?mise en forme automatique Print )
Taylor Scott
Au-delà de cela, et en reconnaissant que votre solution ne prend pas d'entrée via l'appel de sous-routine, cela peut ensuite être converti en une fonction de fenêtre immédiate VBE pour 50 octets While x<=[A1]:x=x+1:b=IIf([A1]Mod x,b,b+x):Wend:?bqui suppose que x, best la valeur par défaut de 0 et sort dans la fenêtre immédiate VBE (à partir de la fenêtre immédiate VBE ?équivaut à Debug.Print )
Taylor Scott
1

Pyth , 6 octets

s*M{yP

Essayez-le ici!

Pyth n'a pas de diviseurs intégrés, donc je pense que c'est raisonnable.

Explication

s * M {yP - Programme complet avec entrée implicite.

     P - Les facteurs premiers de l'entrée.
    y - L'ensemble de puissance de ses facteurs premiers.
   {- Dédupliquer.
 * M - Carte avec multiplication.
s - Somme.
          - Afficher implicitement le résultat.

Étant donné 20, par exemple, voici ce que fait notre programme après chaque 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.

M. Xcoder
la source
1

Ohm v2 , 2 octets

VΣ

Essayez-le en ligne!

C'est assez simple:

V - Diviseurs.
 Σ - Somme.
M. Xcoder
la source
Merde, tu me battre aussi!
ThePlasmaRailgun
1

Husk , 5 octets

ṁΠuṖp

Essayez-le en ligne!

Comment?

ṁΠuṖp - Programme complet, entrée implicite.

     p - Facteurs premiers.
    Ṗ - Powerset.
   u - Supprimer les doublons.
ṁΠ     - Get the product of each list, sum and implicitly output.

Thanks to Zgarb for the suggestions in chat!

Mr. Xcoder
la source
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
la source
0

Add++, 9 bytes

D,f,@,dFs

Try it online!

I clearly got here too late. This defines a function that gets the factors, then sums them.

caird coinheringaahing
la source
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
la source