Trovare i numeri amicabili in C

inserito nella categorie: C, Varie
marchiato con i tag: , , ,
Teoremapappagallo2008g

Definiamo numeri amicabili due numeri tali che la somma dei loro divisori, escluso il numero stesso, è uguale all’altro e viceversa.

Per  esempio 220, 284 formano una coppia di numeri amicabili, in quanto:

  • 220 è divisibile per 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 e 110 e la loro somma risulta 284;
  • 284 è divisibile per 1, 2, 4, 71, 142 che sommati tra loro restituiscono proprio 220.

In più, se è un numero è amicabile di se stesso, esso viene detto perfetto, come ad esempio il 6, la cui somma dei divisori (1+2+3) risulta il numero stesso.

Cosa centra questo con l’informatica?

Questo:

Il programma (scritto in C) sfrutta un semplice meccanismo di cache che permette di non dover ricalcolare, se non necessario, la somma.
La costante L puo’ essere cambiata a piacere.

Un esempio di output del programma ha restituito questo:
1, 1
6, 6
28, 28
220, 284
496, 496
1184, 1210
2620, 2924
5020, 5564
6232, 6368
8128, 8128
10744, 10856
12285, 14595
17296, 18416
63020, 76084
66928, 66992
67095, 71145
69615, 87633
79750, 88730
100485, 124155
122265, 139815
122368, 123152
141664, 153176
142310, 168730
171856, 176336
176272, 180848
185368, 203432
196724, 202444
280540, 365084
308620, 389924
319550, 430402
356408, 399592

Se hai letto questo articolo, potrebbero interessarti anche:

Commenti (2)

  • Flavio De Stefano scrive:
    30 settembre 2011 alle 15:01

    Hai assolutamente ragione, error mio!

  • Claudio Brandolino scrive:
    30 settembre 2011 alle 10:30

    Ciao! Snippet interessante, ma non sono sicuro di aver capito il motivo dei due ternari alle linee 27 e 28.

    Riassegnare cache[x] a sé stesso ad ogni giro non mi sembra una scelta incredibilmente economica; c’è una ragione in particolare per cui la linea 27 non è semplicemente

    if (!cache[x]) {cache[x] = sumod(x);}

    ?

Commenta anche tu!