Count Square-Free Divisors
In number theory, understanding the properties of integers and their divisors is fundamental. A special type of number, known as a square-free number, plays a significant role in various mathematical concepts and algorithms, including those in cryptography and combinatorics. A positive integer is considered square-free if it is not divisible by any perfect square greater than 1. This means that in its prime factorization, no prime factor appears more than once (i.e., all prime exponents are 1). For example, 6 (2 * 3) is square-free, but 12 (2^2 * 3) is not because it's divisible by 4 (2^2). Your task is to count how many of the positive divisors of a given integer n are square-free.
Implement a function countSquareFreeDivisors that takes a positive integer n and returns the total count of its positive divisors that are square-free.
n: number - A positive integer.number - The count of square-free divisors of n.Examples
Example 1
Input:
n = 12
Output:
4
Note:
The distinct prime factors of 12 (2^2 * 3^1) are 2 and 3. The square-free divisors are formed by taking each distinct prime factor at most once: 1 (2^0 * 3^0), 2 (2^1 * 3^0), 3 (2^0 * 3^1), 6 (2^1 * 3^1). There are 2 distinct prime factors, so 2^2 = 4 square-free divisors.
Example 2
Input:
n = 1
Output:
1
Note:
The number 1 has no prime factors. Its only divisor is 1, which is square-free.
Example 3
Input:
n = 30
Output:
8
Note:
The prime factorization of 30 is 2 * 3 * 5. The distinct prime factors are 2, 3, and 5. Since there are 3 distinct prime factors, there are 2^3 = 8 square-free divisors (1, 2, 3, 5, 6, 10, 15, 30).
Example 4
Input:
n = 72
Output:
4
Note:
The prime factorization of 72 is 2^3 * 3^2. The distinct prime factors are 2 and 3. Since there are 2 distinct prime factors, there are 2^2 = 4 square-free divisors (1, 2, 3, 6).
Constraints
1 <= n <= 10^9N up to 10^9 (e.g., operations roughly proportional to sqrt(N) or log N).n will always be a positive integer.n = 0.Loading editor...