Teaching Kids Programming – Algorithm to Determine Three Divisors Numbers

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 <= 10^4

You can count the number of divisors and just check that they are 3
Beware of the case of n equal 1 as some solutions might fail in it

Algorithm to Check Numbers of Three Divisors

We can go through each factor up to square root of N. Each factor d we get another in the pair which is N/d except when these two are equal. This counting the factors/divisors is similar to that of checking a number to see if it is prime number.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def isThree(self, n: int) -> bool:
        i = c = 2
        while i * i <= n:
            if n % i == 0:
                c += 1
                if i * i != n:
                    c += 1
            i += 1
            if c > 3:
                return False
        return c == 3

class Solution:
    def isThree(self, n: int) -> bool:
        i = c = 2
        while i * i <= n:
            if n % i == 0:
                c += 1
                if i * i != n:
                    c += 1
            i += 1
            if c > 3:
                return False
        return c == 3

The time complexity is O(Sqrt(N)) and the space complexity is O(1).

–EOF (The Ultimate Computing & Technology Blog) —