Sphenic Number

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
1 upvote
Asked in company
Barclays

Problem statement

A Sphenic Number is defined as a positive integer N which can be written as a product of exactly three distinct primes. The first few sphenic numbers are 30, 42, 66, 70, 78, 102, 105, 110, 114, …

Your task is that for a given number N, you have to determine whether it is a Sphenic Number or not.

Example:

Let N = 42
N = 2 * 3 * 7
Here, 2, 3 and 7 are 3 distinct prime numbers. Thus, 42 is a sphenic number.

Let N = 60
N = 2 * 2 * 3 * 5
Here, 2, 3, and 5 are distinct prime numbers, but 2 is repeated twice. A sphenic number is a product of exactly 3 distinct primes. Thus, 60 is not a sphenic number.

Let N = 15
N = 3 * 5
Here, 3 & 5 are only 2 distinct prime numbers but, we need 3 distinct prime numbers. Thus, 15 is not a sphenic number.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer 'T' denoting the number of queries or test cases. 

The first and only line of each input contains an integer 'N'.
Output format: 
For each test case, print ‘Yes’ if the given number is a sphenic number; otherwise, print ‘No’ in a separate line.

The output of each test case should be printed in a separate line.
Note: 
You do not need to print anything, and it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100  
1 <= N <= 10^8

where 'T' is the number of test cases and 'N' is the given integer.
Time Limit: 1 sec.
Sample Input 1:
2
121
138
Sample Output 1:
No
Yes
Explanation:
For test case 1: 
N = 121
N = 11 * 11
As it is not a multiple of 3 distinct prime numbers. Thus, 121 is not a sphenic number.

For test case 2:
N = 138
N = 2 * 3 * 23
As 2, 3 & 23 are 3 distinct prime numbers. Thus, 138 is a sphenic number.
Sample Input 2:
3
78
57
125
Sample Output 2:
Yes
No
No
Hint

The very first approach can be using the sieve of Eratosthenes for doing prime factorization of a number.

Approaches (2)
Sieve

Note: We are using Sieve here but as the constraints are too big, we won't be able to create the sieve array in range of N. Thus, this is only a theoretical explanation.
 

  • We will create a sieve in which each index will be having the smallest prime factor of that number. The sieve will be created only once as a precomputation.
  • Algorithm for creating a sieve is as follows.
  1. Initialize an array of largest possible number size and assign value to each index as that index only that is sieve[i] = i.
  2. Assign all even indices as 2.
  3. Loop: for( i = 3; i * i <= N;  i++ )
    If sieve[i] == i, 
    Loop: for( j = i * i; j <= N; j += i)
    If sieve[j] == j, assign sieve[j] = i
  • Now, as the sieve is created, we can use it to get the smallest prime factor of any number and by further dividing the number by its smallest prime factor, it will lead us to another number which will give the 2nd smallest prime factor. This can be repeated to get the third prime factor as well.
  • Remember: If a number has two consecutive same prime factors or don’t have three prime factors then it is not a sphenic number.
  • Checking for the sphenic number can be done by the following algorithm.
  1. Initialize prev = 0, to store previous prime factor.
  2. Initialize count = 0, to store the count of prime factors.
  3. Loop while N > 1:
    → Initialize factor = sieve[N], this is the very first prime factor. 
    → Increase count, count++
    → Check if prev == factor or count > 3, return false.
    → Assign prev = factor
    → Update N as N / factor
  4. If count == 3, return true.
  5. Otherwise, return false.

Let’s take an example where N = 30

  1. Initially, prev = 0, count = 0
  2. Now, when the loop starts,

→ First iteration:
As the smallest prime factor of 30 is 2 i.e. sieve[30] = 2, so, we divide 30 by 2 and increase the count to 1 and update prev to 2.

We update 30 with 30 / 2 i.e. 15. 
→ Second iteration:
Now, the smallest prime factor of 15 is 3 i.e. sieve[15] = 3, so, we divide 15 by 3 and increase the count to 2 and update prev to 3.
We update 15 with 15 / 3 i.e. 5.
→ Third iteration:

The smallest prime factor of 5 is 5 i.e. sieve[5] = 5, so, we divide 5 by 5 and increase the count to 3 and update prev to 5.
We update 5 with 5 / 5 i.e. 1.

As, N becomes equal to 1, so, while loop will be ended and as the count is equal to 3, it is a sphenic number.

 

Time Complexity

The time complexity analysis can be done as follows: 

 

Pre Computation time:

O(Nlog(log(N)) where N is the largest possible number(constraint). For more information, you may refer here. 

 

Approach time: 

O(1), per test case.

In the worst case, the loop will run for at max 3 times which is constant.

Note: This is a very fast algorithm for small values of N.

Space Complexity

The space complexity analysis can be done as follows: 

 

Pre Computation time:

O(N) where N is the largest possible number(constraint).
In the worst case, we need to create an array of size N. 

 

Approach time: 

O(1), per test case.

In the worst case, only constant extra space is used. 

Code Solution
(100% EXP penalty)
Sphenic Number
Full screen
Console