Perfect Numbers up to N

medium Number Problems

Problem

Read an integer n and print all perfect numbers from 1 to n on one line. A perfect number equals the sum of its divisors that are smaller than itself (28 = 1 + 2 + 4 + 7 + 14). Print an empty line if there is none.

Constraints

  • 1 <= n <= 10^5

Examples

Input

500

Output

6 28 496

Solutions

Best approachTime O(n * sqrt(n))Space O(1)

We combine the fast perfect-number test (divisor pairs up to the square root) with a loop over all numbers.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : List all perfect numbers from 1 to n.
 * Input   : One integer n.
 * Output  : The perfect numbers on one line, separated by a space.
 * Approach: Find the divisors of each number up to its square root.
 * Time    : O(n * sqrt(n))
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method receives a number and returns true if it is a perfect number.
    static boolean isPerfect(int number) {
        if (number < 2) {
            return false;
        }
        // The divisor 1 divides every number. Then we add divisor pairs up to the square root.
        int sum = 1;
        for (int divisor = 2; divisor * divisor <= number; divisor++) {
            if (number % divisor == 0) {
                sum = sum + divisor;
                if (divisor != number / divisor) {
                    sum = sum + number / divisor;
                }
            }
        }
        return sum == number;
    }

    public static void main(String[] args) {
        int limit = new Scanner(System.in).nextInt();
        StringBuilder result = new StringBuilder();

        // Step 1: Test every number from 1 to the limit.
        for (int number = 1; number <= limit; number++) {
            // Step 2: Keep the number if it is perfect. Put one space between the numbers.
            if (isPerfect(number)) {
                if (result.length() > 0) {
                    result.append(" ");
                }
                result.append(number);
            }
        }

        // Step 3: Print the list.
        System.out.println(result);
    }
}
Hints (1)
  1. Reuse the perfect number method.