He ain't no Ramanujan

It is just okay to check all the way up to $\sqrt{n}.$

Note that the factors occur in pairs $(a,b)$ where $n=ab.$

Now, either $a$ or $b$ is less than or equal to $\sqrt{n}$ . If it were not, then their product would be greater than $\sqrt{n} \cdot \sqrt{n}=n$ , and $n\ne ab.$

Thus, for every factor that is greater than or equal to $\sqrt{n}$ , there exists another factor which is less than or equal to $\sqrt{n}.$

At first I thought it was $\frac{1}{2}n$ , but no! It is actually $\sqrt{n}$ . If a number $n$ is not a prime, it can have two factors, say, $a$ and $b$ and $n=ab$ . If both $a>\sqrt{n}$ and $b>\sqrt{n}$ , then $ab>n$ . Therefore the largest factor should be $\boxed{\sqrt{n}}$ .

In fact you should only need to check whether n is divisible by all prime numbers in 2 to sqrt(n) inclusive. Having said that - if you had a table of prime numbers available I guess you wouldn't need the programme in the first place! You could still speed it up by only checking for divisibility by 2 and all odd numbers in the range since all primes are odd except 2.

If $\ c= ab$ and WLOG $\ a \leq b$ then $\ a \leq\sqrt{n}$ therefore we only need to check factors up to $\sqrt{n}$ as it must contain a factor ${a}$ that is less than or equal to ${n}$

It's called the Sieve of Eratosthenes .

Because all factors come in pairs (squares have a repeated factor), the largest factor you need to check is root n since one of the pair will be at most root n.