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

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

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);
          }
      }
  }

Solution

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.