2
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ By "perfect number", do you mean a number which is the sum of all its proper divisors, $n = \sum_{d|n,d\lt n} d$? Of course six is one such number, $6=1+2+3$. $\endgroup$ – hardmath May 29 '18 at 14:29
  • $\begingroup$ @hardmath < Yes, exactly. $\endgroup$ – itsnotmyrealname May 29 '18 at 14:30
  • $\begingroup$ Note that for finding perfect numbers, no one has ever found an odd perfect number. The question if one exists is "open". The exact form of even perfect numbers is known, and they have many factors of two. In that sense it is a good idea to test for an even perfect number by dividing out as many factors of two as possible. See this previous Question How to check for perfect numbers? and its answers for more details, involving Mersenne primes. $\endgroup$ – hardmath May 29 '18 at 14:46
  • $\begingroup$ Note: to find all of the prime factors, it is sufficient to go up to SQRT(n). To find all factors, it is faster to first find all of the prime factors and then use them to generate all of the factors. $\endgroup$ – RBarryYoung May 29 '18 at 20:54
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thank you. But, what about $6$? $\sqrt 6 = 2.44$ Should we ceil the number to get half border which is $3$? $\endgroup$ – itsnotmyrealname May 29 '18 at 14:38
  • $\begingroup$ @itsnotmyrealname The argument I gave shows that you never have to check anything greater than $\sqrt n$ (since one of the factors must be less or equal to than $\sqrt n$), so we don't have to check $3$ in this case: just $1$ and $2$. Checking $1$ gives us $1$ and $6$; checking $2$ gives us $2$ and $3$. $\endgroup$ – BallBoy May 29 '18 at 14:40
  • $\begingroup$ @itsnotmyrealname Another comment: the savings are much larger for larger $n$. The next known perfect number is $n=28$. By the $\sqrt n$ method, we have to check only up to (and including) $5$, which is much less than the $14$ we'd need to check by the $\frac n2$ method! Try it and see if you can show that $28$ is perfect. $\endgroup$ – BallBoy May 29 '18 at 14:41
  • $\begingroup$ Gotcha what you mean. You can glance at it, ideone.com/VYKxup $\endgroup$ – itsnotmyrealname May 29 '18 at 15:00
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I realized it early. Thank you for your algorithm. There are a host of code snippets etc. but I wanted to get what there exist in underneath. $\endgroup$ – itsnotmyrealname May 29 '18 at 15:10
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$\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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.