Why is finding factors until half of the number enough?

Question

If I want to find factors of a number except itself, at first I think that I divide it the number in turn $1, 2, 3, ... , n - 1$. However, after a while, noticed that division to get the factors is sufficient up to $n/2$(inclusive). The rest part is not needed. What is its reason? Why is it enough to find them? How can it be explained?

@Edit, to find prime number until $\sqrt n$ is sufficient, but what about perfect numbers? I think $n/2$ is good way to go perfect numbers?

For 6,
1   2   3   4   5
^
    ^
        ^|
           Up to here, it's ok.

Answer 1

Edit: Saw you edited the question and added some comments at the end of my answer to address.

There can't possibly be any factors between $\frac n2$ and $n$. Suppose $\frac n2 < a < n$ and $a \cdot b = n$. What could $b$ be? If $b=1$, then $a \cdot b = a < n$. If $b \geq 2$, then $a \cdot b > \frac n2 \cdot 2 = n$. So $b$ can't be any positive integer; thus $a$ isn't a factor of $n$.

In fact, as long as you list both factors when you do the division, you can stop testing at $\sqrt n$. That's because it's impossible for both factors to be greater than $\sqrt n$: if $a,b > \sqrt n$, then $a \cdot b > \sqrt n \cdot \sqrt n = n$. So factors always come in pairs $a \cdot b = n$ with $a < \sqrt n$ and $b > \sqrt n$ (with the exception of $\sqrt n$ itself, if it's an integer). Here's how this method works to find the factors of $10$:

• $3 < \sqrt 10 < 4$, so we can stop testing at $3$
• Test $1$: $\frac{10}1 = 10$, so $10 = 1 \cdot 10$, giving us the two factors $1$ and $10$
• Test $2$: $\frac{10}2 = 5$, so $10 = 2 \cdot 5$, giving us the two factors $2$ and $5$
• Test $3$: $\frac{10}3$ is not an integer so we don't get any factors

Thus the full list of factors is $1,10,2,5$ (or, reordered, $1,2,5,10$)

This method works to find all the factors, not just the prime factors, so it's a perfect method for testing whether a number is perfect (in our example, $1+2+5=8\neq10$, so $10$ is not perfect).

Answer 2

Suppose we can write $n = a*b$, so both $a$ and $b$ are factors. Notice that it must be the case that one of them is less than or equal to $n/2$. To see this, suppose both $a,b > n/2$. Then $a*b > n$, which is absurd. This means for any pair of factors, one of them must be less than $n/2$, hence you need only check up to and including $n/2$ to find them all.

Answer 3

Actually to find the (prime) factors of a whole number $n$, it is enough to check for divisors up to $\sqrt n$. Going up to $n/2$ would be overkill.

One way to think about this is to ask, if $n$ is not a prime but instead composite, how big can the smallest divisor of $n$ be? If we have the factorization $n = a\cdot b$, we cannot have both $a$ and $b$ larger than $\sqrt n$.

To make a complete list of the factors of a whole number $n\gt 1$, you can do it by checking all $1\lt a \lt \sqrt n$ and putting both $a$ and $b$ in your list when the division $n/a = b$ is exact. If $\sqrt n$ happens to be an integer (i.e. $n$ turns out to be a perfect square when we extract $\sqrt n$), then put one copy of that integer in the list of divisors. The list (of proper divisors of $n$) will be complete when you finish by including $1$, which is always a divisor you want in your list.

Answer 4

$\frac{n}{x}<2$ if $x>\frac{n}{2}$. $2$ is the smallest prime. If $x$ was a factor then $x\times \text{something}=n$ where $\text{something}\ge 2$.