Spřátelená čísla - pomoc s programem – C / C++ – Fórum – Programujte.com

Ahoj hoši, tak jsem to zase :) 

Tentokrát jsme dostali za úkol program, který bude detekovat spřátelená čísla.

Spřátelená čísla jsou taková celá kladná čísla, že jedno je rovno součtu vlastních dělitelů čísla druhého. Například čísla 220 a 284 jsou spřátelená, protože:
seznam všech vlastních dělitelů 220:
  1, 2, 4, 5, 10, 11, 20, 22, 44, 55 a 110
  1+2+4+5+10+11+20+22+44+55+110 = 284

a zároveň

seznam všech vlastních dělitelů 284:
  1, 2, 4, 71 a 142
  1+2+4+71+142 = 220

Vstupem programu je horní mez do které se mají dané čísla vypisovat. Výstupem jsou dvojice spřátelených čísel, které jsou řazeny vlevo menší a vpravo větší.

Chtěla jsem se zeptat, zda by mi někdo poradil, jak do toho. Nějakou základní tezi, nebo i s programem pomohl :)

Můžeš postupovat následovně: v cyklu projdeš všechna čísla od začátku až po horní mez. Pro každé číslo (a) spočítáš jeho součet dělitelů (na výpočet si udělej funkci). Pak vezmeš tento součet - toto výsledné číslo (b) - a pro něj taky spočítáš součet dělitelů (c) a výsledek porovnáš s původním číslem (a == c) - pokud se rovnají, tak máš spřátelená čísla (možná optimalizace).

Funkce na výpočet součtu dělitelů bude obsahovat cyklus (pro začátek od 1 do číslo - 1), kde se bude testovat dělitelnost zadaného čísla (zbytek po dělení) a dělitele sčítat (možná optimalizace).

Koukám, že se tu rojí prváci fakult IT :-)

K problému, začal bych tím, že bych sestavil program, který bude testovat všechny možnosti - neboli hrubou silou. A dál už jen přemýšlet jak to optimalizovat.

Hele nechodíš náhodou na FIT? jen že totálně stejný zadání tam je... Pokud příspěvek od "Vágner" je od toho Vágnera co myslim tak si celkem v <|>... Patří ti to :-D nemáš zkoušet podváadět :-D

Řekl bych že ten vágner je nejspíš fejk, ale pokud ne, tak to mas blby

anyway, za pár minut se to dá napsat pomocí několika cyklů brutální silou (takže s 12 body nepočítat)

#11 Kingoz
Jen musím upozornit, že řešení hrubou silou je trošku náročné. Pokud se to změří časově, tak to jsou nechutná čísla - klidně si dojít na oběd :-)

#12 Šťouchal

Jo,  to vím, taky jsem dostal jenom 5 bodů, maximum je 12, ale jsem rád že jsem to napsal vůbec takhle a na optimalizaci nemám čas.

Optimalizaci doporučuji nakreslit na papír - jde to udělat poměrně rychle (v rámci jednotek hodin).