Besedilo naloge
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.
Reševanje 1
Na začetku definiramo funkcijo problem21 z enim parametrom n. Zamislimo si tudi dva seznama. V enem izmed teh dveh seznamov(sez) bo zaporedje vsot vseh pravih deljiteljev(vsi deljitelji števila n, ki niso n) do n. V drugem seznamu bo zaporedje prvih n števil. Seznam sez vnesemo že prve tri elemente, da bo lažje sestaviti kasnejši algoritem. Seznam sez1 definiramo kot prazen. Ta dva seznama bosta uporabna, ko bomo ustvarjali seznam parov naravnih števil do n in vsoto njihovih pravih deljiteljev.
Ustvarimo novo funkcijo, s katero si bomo pomagali izračunati vsoto vseh pravih deljiteljev števila a. Poimenujemo jo vsotaDelj(a), ima en parameter. Na začetku ustvarimo števec in ga nastavimo na 0. Z for zanko gremo čez vsa naravna števila do polovice a, saj nad polovico števila a ni pravih deljiteljev. Za vsako to naravno število z if stavkom preverimo, če je ostanek pri deljenju enak 0. Če je, vsoto povečamo za to število. V tem primeru j. Funkcija kot rezultat vrne vsoto.
Z zanko, ki teče od 4 do n+1, vsoto s pomočjo novoustvarjene funkcije nastavimo na vsoto pravih deljiteljev. Seznamu sez z ukazom sez.append dodamo vse vsote pravih deljiteljev do n+1 v zaporedju.
Z zanko for gremo od 1 do n+1 in dodamo vsa naravna števila v seznam sez1.
Tako smo zapolnili oba seznama.
Reševanje 2
Ustvarimo prazen seznam sez2, ki je namenjen vsem parom iz sez in sez1. Z for zanko dodamo vse pare, kot je prikazano.
Ustvarimo prazen seznam sezPrijatelj, ki je namenjen vsem prijateljskim parom iz seznama sez2. Z for zanko gremo čez vse pare [f,g] in [h,j] in primerjamo če je f enak j in če je g enak h, kar v primeru, da f ni h pomeni, da je program našel prijateljski števili, ki jih doda v sezPrijatelj.
Za konec bomo še izpisali vsoto vseh prijateljskih števil do n. V našem primeru je n = 10000. Ustvarimo števec vsota = 0 in z zanko for, ki gre čez vse elemente v seznamu sezPrijatelj, prišteje vsoti vsak prvi element tega seznama. Funkcija vrne vsoto.
Funkcijo testiramo tako, da jo pokličemo z parametrom 10000.
Končni program
