Count the Divisors
Problem
Read a positive integer and print how many positive divisors it has. Example: 12 has the divisors 1, 2, 3, 4, 6, 12, so the answer is 6.
Constraints
- 1 <= n <= 10^12
Examples
Input
12
Output
6
Solutions
Every divisor d below the square root has a partner n / d above it. So each hit counts as two divisors, except when both are the same number.
/*
* Problem : Count the divisors of a number.
* Input : One positive integer.
* Output : The number of divisors.
* Approach: Count divisor pairs up to the square root.
* Time : O(sqrt(n))
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
long number = new Scanner(System.in).nextLong();
// Step 1: Start the counter at 0.
int count = 0;
// Step 2: Test numbers while divisor * divisor <= number.
for (long divisor = 1; divisor * divisor <= number; divisor++) {
if (number % divisor == 0) {
// Step 3: The divisor and its partner (number / divisor) are two divisors.
// If both are the same number (36 = 6 * 6), count it only once.
if (divisor * divisor == number) {
count = count + 1;
} else {
count = count + 2;
}
}
}
// Step 4: Print the count.
System.out.println(count);
}
}
Hints (2)
- Divisors come in pairs.
- What if the number is a perfect square?