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

**Moshe Zadka
**
moshez@zadka.site.co.il

*Sat, 13 Jan 2001 12:03:25 +0200 (IST)*

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!