Check if given number has 7 divisors

Given a number N, the task is to check whether N has 7 divisors or not.

Examples:

Input: 64
Output: 1 
Explanation: 1, 2, 4, 8, 16, 32, 64 -> 7 divisors so output is 1

Input: 100
Output: 0
Explanation: 1, 2, 4, 5, 10, 20, 25, 50, 100 -> 8 divisors so output is 0

Input: 729
Output: 1
Explanation: 1, 2, 4, 8, 16, 32, 64 -> 7 divisors so output is 1

Approach: The problem can be solved based on the following mathematical observation:

The prime factorization of a number is:
N = p₁^e1 * p₂^e2 * . . . * p_n^en 
So number of divisors = ( e₁ + 1 ) * (e₂ + 1) *. . . * (e_n + 1).

In this case, number of divisors = 7 .
So, ( e₁ + 1 ) * (e₂ + 1) *. . . * (e_n + 1) = 7

7 is multiplication of at most 2 natural numbers. 
So, it can be only written as ( e₁ + 1 ) * (e₂ + 1) = 1 * 7    
So, e₁ = 0  &  e₂ = 6  from above equation.

So, it is clear that for 7 divisors only one case is possible and that is (prime number)⁶. Follow the steps to solve the problem:

• Check if N^(1/6) is a prime number or not.
• If it is prime number then output “Yes”.
• Otherwise, the output will be “No”.

Below is the implementation of the above approach: 

Time Complexity: O(logN)
Auxiliary Space: O(1)