Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Basics

Perfect Number

Easy · Basics · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

A perfect number equals the sum of its proper divisors (all divisors except itself). For example 28 = 1 + 2 + 4 + 7 + 14. Print YES if n is perfect, otherwise NO.

Input

A single integer n.

Output

YES or NO.

Constraints

Divisors come in pairs (d, n/d), so you only need to loop up to √n.

Example 1

Input

28

Output

YES

Example 2

Input

12

Output

NO

Hints

  1. You need the sum of all divisors smaller than n.
  2. Loop d only up to √n and add both d and n/d (once if they are equal).

Approach

Start the sum at 1 (every n > 1 has divisor 1), then for every d from 2 while d·d ≤ n: if d divides n, add d and its partner n/d (only once when d·d = n). Compare the sum with n. 1 is not perfect (its proper-divisor sum is 0). √(10^12) = 10^6 iterations.

Complexity: O(√n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    if (n == 1) {
        cout << "NO\n";
        return 0;
    }
    long long sum = 1;
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            sum += d;
            if (d * d != n) sum += n / d;
        }
    }
    cout << (sum == n ? "YES" : "NO") << "\n";
    return 0;
}

Python solution

n = int(input())
total = 1 if n > 1 else 0
d = 2
while d * d <= n:
    if n % d == 0:
        total += d
        if d * d != n:
            total += n // d
    d += 1
print("YES" if n > 1 and total == n else "NO")

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        if (n == 1) {
            System.out.println("NO");
            return;
        }
        long sum = 1;
        for (long d = 2; d * d <= n; d++) {
            if (n % d == 0) {
                sum += d;
                if (d * d != n) sum += n / d;
            }
        }
        System.out.println(sum == n ? "YES" : "NO");
    }
}

Solve Perfect Number online · All practice problems