# Is there a name for the largest factor $f$ of a number $n$ so that $n/f \ge f$?

TL;DR: Is there a name for the largest value of $$f$$ for which $$f|n$$ and $$n/f \ge f$$? Or a name for the smallest value of $$f$$ for which $$f|n$$ and $$n/f < f$$?

Additional clarification. This question occurred to me while writing a very short piece of code to find the factors of a number and making a small optimisation to it. When you try to find the factors of a number $$n$$ you can simply take each element of the sequence $$1, 2, 3, ..., n$$ and check if $$n$$ is divisible by it. A first optimisation is to limit yourself to possible factors $$f$$ for which $$f <= n/2$$ (yielding only the proper divisors) and add $$n$$ itself to the set. A second optimisation is to stop at the first $$f$$ for which $$n/f < f$$. At that point the remainder of the factors can be found by dividing $$n$$ by each already found factor. I'm interested in knowing whether there's a name for this "pivot" element and its properties.

Examples:

• For 12 the largest such $$f$$ is 3, since the remaining factors can be found by dividing 12 by 1, 2 and 3. The smallest "pivot" would be 4 as at that point $$12/4 < 4$$
• For any prime number $$p$$ the largest $$f$$ so that $$f|p$$ and $$p/f \ge f$$ is 1, and the smallest $$f$$ so that $$f|p$$ and $$p/f < f$$ is $$p$$.
• You could stop checking for factors at the square root of $n$: for example $\sqrt{12} \approx 3.46$. If you are restricted to integers, stop trying at the first potential factor $f$ where $f\times f \gt n$ – Henry Apr 2 at 20:01
• @Henry Thanks mate. I suppose stopping at the first $f$ where $n/f < f$ is kind of equivalent. It would imply one extra check which I'll consider negligible. – G_H Apr 2 at 21:28

## 1 Answer

not sure about names; however, this leads directly into what we call Fermat's method of factoring. Given odd $$n,$$ find $$w =\lfloor \sqrt n \rfloor.$$ Then increase $$w$$ one by one, and just check whether $$w^2 - n$$ is a square. If $$w^2 - n = t^2,$$ then $$w^2 - t^2 = n,$$ and $$n = (w+t)(w-t).$$

Your desired number, the largest factor below $$\sqrt n,$$ would appear as the first $$(w-t).$$

Fermat's is, among really elementary methods, the opposite of checking small prime factors. It is quick if $$n$$ is the product of two numbers (possibly prime) of very similar size

https://en.wikipedia.org/wiki/Fermat%27s_factorization_method

• Thanks for the explanation and link. Optimisation and algorithms aside though, I'm just wondering if there's a specific term for this point at which the remaining factors are derivative of the ones already found. – G_H Apr 2 at 21:30