Frontend School

Count Square-Free Divisors

DSA
easy

Count Square-Free Divisors

Easy
Math
Number Theory
Divisors
Prime Factorization

Overview

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.

What you need to do / Task

Implement a function countSquareFreeDivisors that takes a positive integer n and returns the total count of its positive divisors that are square-free.

Input & output

  • Input: n: number - A positive integer.
  • Output: number - The count of square-free divisors of n.

Clarifications

  • The number 1 is considered square-free, as it has no prime factors, and thus no prime factor appears more than once. It is also a divisor of every positive integer.
  • Prime numbers are always square-free. Their only divisors are 1 and themselves, both of which are square-free.

Examples

1

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.

2

Example 2

Input:

n = 1

Output:

1

Note:

The number 1 has no prime factors. Its only divisor is 1, which is square-free.

3

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).

4

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

Constraints & assumptions

  • 1 <= n <= 10^9
  • The solution should be efficient enough to pass within typical time limits for N up to 10^9 (e.g., operations roughly proportional to sqrt(N) or log N).
  • You can assume n will always be a positive integer.

Out of scope

  • Handling negative inputs or n = 0.
  • Advanced number theoretic algorithms like Pollard's rho or Miller-Rabin primality test. A basic prime factorization approach is expected.

What interviewers evaluate

  • Correctness: The solution must accurately count all square-free divisors for all valid inputs.
  • Efficiency: The chosen algorithm should be performant for the given constraints, demonstrating an understanding of time complexity.
  • Number Theory Concepts: Proper application of prime factorization and the definition of square-free numbers.
  • Code Quality: The code should be well-structured, readable, and maintainable.

Loading editor...