# Perfect Number

Posted: 31 Dec, 2020

Difficulty: Easy

#### You are given a positive integer K. Your task is to find out whether K is a perfect number or not.

##### Note :

```
Perfect numbers are those numbers that are equal to the sum of all its proper divisors.
Proper divisors are all the divisors of a number excluding the number itself.
```

##### For example :

```
For K = 6, the proper divisors of 6 are 1, 2, 3 and its sum is 6 so 6 is a perfect number. For K = 8, the proper divisors of 8 are 1, 2,4 and its sum is 7 so 8 is not a perfect number.
```

##### Input format :

```
The first line of input contains a single integer T, representing the number of test cases.
The first and the only line of each test case contains a single positive integer K, as described in the problem statement.
```

##### Output Format :

```
For each test case, return true if K is a perfect number or else return false.
```

##### Note :

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

##### Constraint :

```
1 <= T <= 100
2 <= K <= 10^8
Time Limit: 1 sec
```

##### Follow Up :

```
Can you do this in O(sqrt(N)) time and constant space?
```

Approach 1

Approach 2

- One key observation is the divisor occurs in pairs. Let say A and B are two number and A * B = K, let’s say that A < sqrt(K) then B should be greater than sqrt(K). So it is enough to iterate through numbers less than or equal to sqrt(k) to get all of its divisors.
- Iterate through all the numbers from 1 to sqrt(K), let's say we are currently at ith number and k is divisible by i then add both i and k/i to the sum.
- If the sum of all proper divisors is equal to k then return true else return false.
- In case of i == 1 or i == sqrt(K) just add i to the sum and not k/i.