perfektno stevilo

Yo


Jaz mam problem pri teli nalogi. Bom kr celo napisal.

Napisi funkcijo, ki za dano pozitivno celo število pove, če je število perfektno. Neko število je perfektno, če je vsota svojih deliteljev brez samega sebe. Prime: Število 6=1+2+3 je perfektno.


Drugač sm tko mal premisljeval kva bi naredu, pa mi je tko neki prslo v misel da je neki v zvezi ostanki pr deljenju z svojimi delitelji. Sm to se mi zdi mal cudn.


Vseen hvala ce bo kdo pomagal.

narobe sem razmišljal ;)

Bi morda šlo bolje če bi razčlenil problem na manjše enote; če ti uspe napisati spodnje funkcije (imena in sintaksa so simbolna, saj nisem zasledil jezika v katerem programiraš) ti bo zagotovo uspelo sestaviti celotno rešitev:

1) int arraySum( arrayOfInts ), ki vrne vsoto števil v polju arrayOfInts

2) bool dividesInt( int1, int2 ), ki preveri ali int2 deli int1? (namig: uporaba operatorja %, ki vrne ostanek pri celoštevilskem deljenju)

in z uporabo 2) še
3) array getDividersOfInt( int1 ), ki vrne array vseh deljiteljev števila int1

LP, r

The Euclid-Euler Theorem

But how have mathematicians been able to discover these perfect numbers? Crilly says that the combined work of two mathematicians, who lived 2000 years apart, provides the answer. Their names were Euclid of Alexandria and Leonhard Euler and their formula, 2^(n−1) X (2n − 1), ^ indicates 'to a power of', known as the Euclid-Euler Theorem, would unlock the secret to generating perfect numbers.
Mersenne Primes

Every good lock must have a key and it was the findings of a French monk named Father Marin Mersenne that would provide the key to Euclid and Euler’s Theorem. Crilly noted that Father Mersenne had worked with numbers generated by 2 to a power, minus 1, or (2^n) -1. These Mersenne numbers include

* 2^1-1=2-1=1
* 2^2-1=4-1=3
* 2^3-1=8-1=7
* 2^4-1=16-1=15
* 2^5-1=32-1=31

Insert a prime Mersenne number into the Euclid-Euler Theorem and the result is a Perfect Number.
Other Facts About Perfect Numbers

With the exception of 6, a perfect number divided by 9 gives remainder 1. All perfect numbers can be arrived at by adding consecutive numbers i.e 1+2+3 … and ending with a Mersenne prime.

je pa algoritem, khm, eksponenten (O(e^i), kjer je i=log n, kolikor potrebujemo, da zapišemo n).

e^i, kjer je i=log n je e^(log n) = n,

tako da algoritem ni eksponenten, ampak kar O(n) (zraven pride kvecjemu se kaksna konstanta, ce log nima osnove e).