Factors of a Number
Problem
Read a positive integer and print all its factors (divisors) in ascending order on one line, separated by a space.
Constraints
- 1 <= n <= 10^12 for the pair version, 1 <= n <= 10^7 for the simple version
Examples
Input
12
Output
1 2 3 4 6 12
Solutions
We test all numbers from 1 to n. It is simple, but it takes n steps.
/*
* Problem : List all factors of a number.
* Input : One positive integer.
* Output : All factors in ascending order on one line.
* Approach: Test every number from 1 to n.
* Time : O(n)
* Space : O(k)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
long number = new Scanner(System.in).nextLong();
StringBuilder result = new StringBuilder();
// Step 1: Try every number from 1 to the number itself.
for (long divisor = 1; divisor <= number; divisor++) {
// Step 2: If the number divides without remainder, it is a factor.
if (number % divisor == 0) {
// Step 3: Add the factor to the result. Put one space between factors.
if (result.length() > 0) {
result.append(" ");
}
result.append(divisor);
}
}
// Step 4: Print all factors on one line.
System.out.println(result);
}
}
Hints (1)
- A factor divides the number with remainder 0.