[Tutor] [Edu-sig] collection of ACM programming problems (fwd)

[Moshe Zadka]

On Fri, 12 Jan 2001, Jose Amoreira <amoreira@mercury.ubi.pt> wrote:

> Sorry to drop in, but I thought that you just have to go up to the *square
> root* (instead of half) of the tested number. This is not a formal
> demonstration, but if the tested number devides evenly by its half, it also
> devides evenly by 2, wich comes first in this increasing series of devides.

You're right, and here's a formal one:

suppose a*b = n. Then either a or b are <=sqrt(n), otherwise
	a  > sqrt(n)
	b  > sqrt(n) ==>
   n = a*b > sqrt(n)*sqrt(n) = n

which is a contradiction.
QED.
-- 
Moshe Zadka <sig@zadka.site.co.il>
This is a signature anti-virus. 
Please stop the spread of signature viruses!