Welcome to Subscribe On Youtube

1952. Three Divisors

Description

Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.

An integer m is a divisor of n if there exists an integer k such that n = k * m.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= n <= 104

Solutions

Solution 1: Direct Implementation

A number $n$ must have two positive divisors, $1$ and $n$. Therefore, you only need to enumerate the numbers between $2$ and $n-1$ to see if they are positive divisors of $n$. If so, accumulate the counter and finally determine whether the counter is $1$. That’s it.

Time complexity $O(n)$, space complexity $O(1)$. Where $n$ is the given integer.

Solution 2

We can enumerate the numbers $i$ between $1$ and $\sqrt{n}$. If $n$ is divisible by $i$ and $\frac{n}{i}$ is not equal to $i$, then the counter accumulates $2$, otherwise the counter accumulates $1$. Finally, determine whether the counter is $3$.

Time complexity $O(\sqrt{n})$, space complexity $O(1)$. Where $n$ is the given integer.

• Java
• C++
• Python
• Go
• Javascript

• class Solution {
      public boolean isThree(int n) {
          int cnt = 0;
          for (int i = 2; i < n; i++) {
              if (n % i == 0) {
                  ++cnt;
              }
          }
          return cnt == 1;
      }
  }
  
  
  // Solution 2
  class Solution {
      public boolean isThree(int n) {
          int cnt = 0;
          for (int i = 1; i <= n / i; ++i) {
              if (n % i == 0) {
                  cnt += n / i == i ? 1 : 2;
              }
          }
          return cnt == 3;
      }
  }
  
  

• class Solution {
  public:
      bool isThree(int n) {
          int cnt = 0;
          for (int i = 2; i < n; ++i) {
              cnt += n % i == 0;
          }
          return cnt == 1;
      }
  };
  
  
  // Solution 2
  class Solution {
  public:
      bool isThree(int n) {
          int cnt = 0;
          for (int i = 1; i <= n / i; ++i) {
              if (n % i == 0) {
                  cnt += n / i == i ? 1 : 2;
              }
          }
          return cnt == 3;
      }
  };
  
  

• class Solution:
      def isThree(self, n: int) -> bool:
          return sum(n % i == 0 for i in range(2, n)) == 1
  
  
  # Solution 2
  class Solution:
      def isThree(self, n: int) -> bool:
          cnt = 0
          i = 1
          while i <= n // i:
              if n % i == 0:
                  cnt += 1 if i == n // i else 2
              i += 1
          return cnt == 3
  
  

• func isThree(n int) bool {
  	cnt := 0
  	for i := 2; i < n; i++ {
  		if n%i == 0 {
  			cnt++
  		}
  	}
  	return cnt == 1
  }
  
  
  // Solution 2
  func isThree(n int) bool {
  	cnt := 0
  	for i := 1; i <= n/i; i++ {
  		if n%i == 0 {
  			if n/i == i {
  				cnt++
  			} else {
  				cnt += 2
  			}
  		}
  	}
  	return cnt == 3
  }
  
  

• /**
   * @param {number} n
   * @return {boolean}
   */
  var isThree = function (n) {
      let cnt = 0;
      for (let i = 2; i < n; ++i) {
          if (n % i == 0) {
              ++cnt;
          }
      }
      return cnt == 1;
  };
  
  
  // Solution 2
  /**
   * @param {number} n
   * @return {boolean}
   */
  var isThree = function (n) {
      let cnt = 0;
      for (let i = 1; i <= n / i; ++i) {
          if (n % i == 0) {
              cnt += ~~(n / i) == i ? 1 : 2;
          }
      }
      return cnt == 3;
  };
  
  

All Problems

All Solutions