Anonymní profil retriwr – Programujte.com

To Grungy :
Je zbytečné procházet čísla tak daleko, stačí do půlky. Těžko asi najdeš menšího dělitele než 2 (s výjimkou 1, ale ta dělí i prvočísla, takže ji neuvažuji) a pokud jím vydělíš zadané číslo, dostaneš právě tu půlku. Každé vyšší číslo už musí být pro dosažení zadaného vynásobeno (reálným) číslem menším než 2, tedy se nejedná o dělitele (kromě samotného čísla, které ale neuvažuji ze stejného důvodu jako číslo 1).
Možná se to lépe vysvětlí na příkladě - pokud mám zadané číslo 100, můžu dojít k rozkladům (1*100) 2*50, 4*25, 5*20, 10*10, od 51 do 99 tam není vůbec nic.
Možná někdo vymyslí i další vylepšení, ale myslím, že už by to potřebovalo složitější úvahy a nějaké podmínky, toto je celkem jednoduché a ušetří polovinu výpočtů.
Jinak při tomto zadání se mi matně vybaví pojem "Erastenovo síto", bohužel už vůbec netuším, oč jde a zdali se to týká tématu, ale pokud si chce někdo zagooglit, třeba to pomůže.