Perfect Numbers up to N
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
We combine the fast perfect-number test (divisor pairs up to the square root) with a loop over all numbers.
/*
* 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)
- Reuse the perfect number method.