why do we iterate to root(n) to check if n is a perfect number

Question

while checking if a number n is perfect or not why do we check till square root of (n)?

also can some body explain the if conditions in the following loop

  for(int i=2;i<sqrt(n);i++)
  {
      if(n%i==0)
      {
          if(i==n/i)
          {
              sum+=i;  //Initially ,sum=1
          }
          else
          {
            sum+=i+(n/i);
          }
      }
  }

If you print the factors after `sqrt(n)`, they would be same as the previous ones in the reverse order. — Wander3r, Jun 07 '21 at 06:24

score 3 · Answer 1 · answered Jun 07 '21 at 06:35

According to number theory, any number has at least 2 divisors (1, the number itself), and if the number A is a divisor of the number B, then the number B / A is also a divisor of the number B. Now consider a pair of numbers X, Y, such that X * Y == B. If X == Y == sqrt(B), then it is obvious that X, Y <= sqrt(B). If we try to increase Y, then we have to reduce X so that their product is still equal to B. So it turns out that among any pair of numbers X, Y, which in the product give B, at least one of the numbers will be <= sqrt(B). Therefore it is enough to find simply all divisors of number B which <= sqrt(B).

As for the loop condition, then sqrt(B) is a divisor of the number B, but we B / sqrt(B) is also a divisor, and it is equal to sqrt(B), and so as not to add this divisor twice, we wrote this if (but you have to understand that it will never be executed, because your loop is up to sqrt(n) exclusively).

thanks for explaining(sorry i was not able to reply earlier since website was down) — coder_newbie, Jun 09 '21 at 08:08

Hans Olsson · Answer 2 · 2021-06-07T08:56:22.760

0

The code uses the trick of finding two factors at once, since if i divides n then n/i divides n as well, and normally adds both of them (else-clause).

However, you are missing the error in the code: it loops while i<sqrt(n) but has code to handle i*i=n (the then-clause - and it should only add i once in that case), which doesn't make sense as both of these cannot be true at the same time.

So the loop should be to <=sqrt(n), even if there are no square perfect numbers. (At least I haven't seen any square perfect numbers, and I wouldn't be surprised if there's a simple proof that they don't exist at all.)

edited Jun 07 '21 at 08:56

answered Jun 07 '21 at 06:38

Hans Olsson

11,123
15
38

1

`i <= n / i` rather than `i <= sqrt(n)` avoids the `sqrt` call, and `int` overflow. – Bathsheba Jun 07 '21 at 06:42
Yes, but sqrt(n) is only done once so the performance cost is small (although most compilers will compute n%i and n/i together so using n/i isn't that bad either). The real problem with sqrt is if you use 64-bit integers or multi-precision where sqrt(n) may be inaccurate or non-existent. – Hans Olsson Jun 07 '21 at 08:54
Under IEEE754 `sqrt` indeed must return the best possible value (note that there are no guarantees for `pow`), so you do have a point. But you are relying on your toolset obeying the rules and IEEE754 is by no means guaranteed so the introduction of `sqrt` is the end of true portability. Personally I don't like introducing floating point functions into integer problems, and will always look for an alternative. And in this case there is a good alternative. – Bathsheba Jun 07 '21 at 09:20
Relying on IEEE754 is in general safe, unless you are on same strange embedded device - which would be weird here. The major problem IMO is that if you really want to investigate perfect numbers you need to look at larger numbers, which means multi-precision and that's why floating point doesn't work - and you should also redesign the entire algorithm as looping to sqrt(n) takes too long time. – Hans Olsson Jun 07 '21 at 09:57

silverfox · Accepted Answer · 2021-06-07T09:35:28.173

It's pretty simple according to number theory:

If N has a factor i, it'll also has a factor n/i (1)
If we know all factors from 1 -> sqrt(n), the rest can be calculated by applying (1)

So that's why you only have to check from 1 -> sqrt(n). However, you code didn't reach the clause i==n/i which is the same as i == sqrt(n), so if N is a perfect square, sqrt(n) won't be calculated.

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n; cin >> n;
    int sum = 1;
    for(int i=2;i<sqrt(n);i++)
    {
        if(n%i==0)
        {
            if(i==n/i) { sum+=i; }
            else { sum+=i+(n/i); }
        }
    }
    cout << sum;
}

Input : 9

Output : 1

As you can see, the factor 3 = sqrt(9) is missed completely. To avoid this, use i <= sqrt(n), or to avoid using sqrt(), use i <= n/i or i*i <= n.

Edit :

As @HansOlsson and @Bathsheba mentioned, there're no odd square which are perfect number (pretty easy to prove, there's even no known odd perfect number), and for even square, there's a proof here. So the sqrt(n) problem could be ignored in this particular case.

However, in other cases when you just need to iterate over the factors some error may occurred. It's better using the right method from the start, than trying to track bugs down afterward when using this for something else.

A related post : Why do we check up to the square root of a prime number to determine if it is prime?

But a prime squared is never a perfect number. In that sense the code is not defective. — Bathsheba, Jun 07 '21 at 09:25
@Bathsheba of course, but in other cases when you just need to iterate over the factors some error may occurred. It's better using the right method from the start, than trying to track little bugs down afterward. — silverfox, Jun 07 '21 at 09:27
I agree with you but think it's worth your pointing it out, rather than my doing so with a snarky comment ;-) — Bathsheba, Jun 07 '21 at 09:29

why do we iterate to root(n) to check if n is a perfect number

3 Answers3