#1952

Easy

LeetCode Problem Workspace

Three Divisors

Determine if a given integer has exactly three positive divisors.

Problem Statement

Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false. A divisor m of n is a number such that there exists an integer k, where n = k * m.

For example, the number 4 has three divisors: 1, 2, and 4. On the other hand, 2 only has two divisors: 1 and 2. If n has more or fewer than three divisors, the answer is false.

Examples

Example 1

Input: n = 2

Output: false Explantion: 2 has only two divisors: 1 and 2.

Example details omitted.

Example 2

Input: n = 4

Output: true Explantion: 4 has three divisors: 1, 2, and 4.

Example details omitted.

Constraints

1 <= n <= 104

Solution Approach

Brute Force Approach

One solution is to count all divisors of n and check if their total is exactly three. This involves iterating over all numbers from 1 to n and checking divisibility.

Efficient Check Using Prime Squares

A more efficient approach is recognizing that if a number has exactly three divisors, it must be the square of a prime number. Check if n is a perfect square and if its square root is prime.

Optimized Divisor Counting

Count divisors only up to the square root of n. For each divisor i, both i and n/i are divisors. Check if the total count equals three.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The brute force approach has a time complexity of O(n), as we must check every number up to n. The prime square approach has a time complexity of O(√n), as we check if n is a perfect square and whether the square root is prime. The optimized divisor counting approach has a time complexity of O(√n), as it counts divisors efficiently.

What Interviewers Usually Probe

This problem tests understanding of divisors and properties of numbers.
Look for efficient approaches that minimize unnecessary calculations.
The candidate should recognize patterns in the number's divisors and use optimizations such as prime checking.

Common Pitfalls or Variants

Common pitfalls

Forgetting that n must be the square of a prime number to have exactly three divisors.
Incorrectly counting the divisors of non-perfect squares.
Missing optimizations that improve runtime, such as only checking divisors up to √n.

Follow-up variants

Test with larger values of n, such as 10^4.
Consider n values that are squares of prime numbers.
Examine cases where n has more than three divisors.

FAQ

What is the key insight to solve the Three Divisors problem?

The key insight is recognizing that a number with exactly three divisors must be the square of a prime number.

How can I optimize the divisor counting method for this problem?

You can optimize the divisor counting by only checking divisors up to the square root of n.

What pattern does the Three Divisors problem test?

It tests your understanding of divisors and number theory, specifically the properties of squares of prime numbers.

What is the time complexity of the brute force approach?

The time complexity of the brute force approach is O(n), as it requires checking every number up to n.

Can n be larger than 10^4?

The problem constraint is 1 <= n <= 10^4, but variations may test larger values of n.

terminal

Solution

Solution 1

#### Python3

1

2

3

class Solution:
    def isThree(self, n: int) -> bool:
        return sum(n % i == 0 for i in range(2, n)) == 1

Solution 2

#### Python3

1

2

3

class Solution:
    def isThree(self, n: int) -> bool:
        return sum(n % i == 0 for i in range(2, n)) == 1

Continue Practicing

#2427 number of common factors #2761 prime pairs with target sum #2947 count beautiful substrings i