[Tutor] [Edu-sig] collection of ACM programming problems (fwd)
Sat, 13 Jan 2001 12:03:25 +0200 (IST)
On Fri, 12 Jan 2001, Jose Amoreira <firstname.lastname@example.org> 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.
Moshe Zadka <email@example.com>
This is a signature anti-virus.
Please stop the spread of signature viruses!