Last Updated: 14 Dec, 2020

Sphenic Number

Moderate

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 Approach

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.
Initialize an array of largest possible number size and assign value to each index as that index only that is sieve[i] = i.
Assign all even indices as 2.
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.
Initialize prev = 0, to store previous prime factor.
Initialize count = 0, to store the count of prime factors.
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
If count == 3, return true.
Otherwise, return false.
Let’s take an example where N = 30
Initially, prev = 0, count = 0
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.

Solve now

02 Approach

We will do the prime factorization of N by dividing it by its factors smaller than its square root. And at last, we will be left with its largest prime factor of N. Thus, we will check for the count of prime factors to be equal to 2 and not 3.

Algorithm for the same will be
Initialize count = 0, to store count of factors.
Loop: for( i = 2; i * i <= N; i++ ):
If N is divisible by i i.e. we found a prime factor of N:
→ Increase count by 1.
→ Divide N by i i.e. N = N / I
→ If count >= 3 or N is divisible by i, this point is checking if the prime factors are more than 3 or if the prime factors are repeated, thus, return false
If count == 2, return true.
Otherwise, return false.
Let’s take an example where N = 42
Initialize count = 0
Now when loop starts
→ First iteration i = 2:

As 42 is divisible by 2, so we divide 42 by 2. Thus, N = 21

Increase count to 1

Now 21 is not divisible by 2, this means, till now it can be considered as Sphenic number.

→ Second iteration i = 3:

As 21 is divisible by 3, so we divide 21 by 3. Thus N = 7

Increase count to 2

Now 7 is not divisible by 3, this means, till now it can be considered as Sphenic number.

→ We exit the loop on the third iteration as i = 4 and 4*4 is greater than 7.

Now as the count is equal to 2, so it is a sphenic number.

Solve now