Can you tell why you don't need to go further than 4 to find the factor of 15?

Answer 1

Half of the factors of a number are less than the square root, half more. Once you have tested numbers up to the square root, you don't have to go any farther. Since 4 x 4 = 16, half of fifteen's factors will be less than 4.

Answer 2

The general rule is that you need only look as far as the square root of your target number. And the proof of this statement follows:

Suppose your target number is n, and suppose s = sqrt(n) so that s*s = n.

Then f is a factor of n if there is a number g such that f*g = n.

then f*g = s*s [since both = n]

this is equivalent to f/s = s/g [divide both sides by g*s]

Now, either (a) f/s <= 1 or (b) f/s >1.

If (a) f/s <= 1 then f <= s

and if (b) f/s > 1 then s/g > 1 [the two ratios are equal] so that s > g

In either case, then, there is factor that is smaller than or equal to s, the square root of n.