This page is still under construction.

Parts of this page are still being built. What you see may change.

Perfect Number Check

Interview

Time limit2sMemory limit128 MB

Summary
Decide whether each given integer equals the sum of its proper divisors and print the equation or a negative verdict.
Level

Easy2 of 10

Topics
Number theory, Implementation
Solved
No attempts yet

Problem

A number nn is a perfect number if it equals the sum of all its divisors except itself.

For example, 6=1+2+36 = 1 + 2 + 3, so 66 is perfect.

Write a program that decides whether nn is a perfect number.

Input

The input holds several test cases, one integer nn per line (2<n<100,0002 < n < 100{,}000).

The last line of the input is −1-1, and that line is not processed. The number of test cases is not given in advance.

Output

Print one line per test case.

If nn is perfect, print it as n = d1 + d2 + ... + dk, where d1<d2<⋯<dkd_1 < d_2 < \cdots < d_k are the divisors of nn other than nn itself, in ascending order. Put one space on each side of the equals sign and of every plus sign.

If nn is not perfect, print n is NOT perfect.

Examples1

  1. Example 1

    Input
    6
    12
    28
    -1
    
    Expected output
    6 = 1 + 2 + 3
    12 is NOT perfect.
    28 = 1 + 2 + 4 + 7 + 14