Approach 1
We will use a bruteforce approach to solve this problem. Identify all the factors of the given number and check each pair if they satisfy the given criteria.
Algorithm
 Take the input number 'N'.

Run a loop till sqrt(N) with variable X and do the following:
 If ‘N’ is not divisible by ‘X’, continue.
 Check if one of ‘X’ and ‘N/X’ is prime and the other one is composite.
 If the above condition is true, output Yes and return.
 Otherwise, the output is No.
Program
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// Function to check if a number is prime.
bool isPrime(int N)
{
if (N == 0  N == 1)
return false;
for (int i = 2; i < sqrt(N) + 1; i++)
{
if (N % i == 0)
return false;
}
return true;
}
// To find any such representation as mentioned in the problem statement.
bool isRepresentable(int N)
{
// Traversing through the array.
for (int i = 2; i < sqrt(N) + 1; i++)
{
if (N % i == 0)
{
if (isPrime(i) && !isPrime(N / i))
{
return true;
}
else if (isPrime(N / i) && !isPrime(i))
{
return true;
}
}
}
return false;
}
// Driver Code
int main()
{
int N;
cin >> N;
if (isRepresentable(N))
{
cout << "Yes";
}
else
{
cout << "No";
}
return 0;
}
Input
6
Output
No
Time Complexity
The time complexity of the above approach is O(N), where ‘N’ is the input number.
It is because for each iteration, we are doing at most O(sqrt(N)) work, hence total time complexity = O(sqrt(N) * sqrt(N)) = O(N).
Space Complexity
The space complexity of the above approach is O(1).
As we are using constant space to execute the algorithm.
Approach 2
Here we will discuss the efficient approach to solve this problem. We will identify all the prime numbers up to 'N'. This can be done in O(N) time using Sieve of Eratosthenes. Next, we will run a loop till the square root of 'N' and search for a number 'X' which satisfies the following conditions:
 'X' divides 'N' and is a prime.
 'N/X' is a composite number.
Algorithm
 Take the input number 'N'.
 Run the Sieve of Eratosthenes algorithm to identify all prime numbers up to 'N' and store them in a boolean array 'IS_PRIME.'

Run a for loop with variable 'X' till 'N'  1 and check for the following:

If 'X' divides 'N':
 Check if 'IS_PRIME[X]' is true and 'IS_PRIME[N/X]' is false.
 Else if 'IS_PRIME[n/X]' is true and 'IS_PRIME[X]' is false.
 If any of the above conditions is true, the answer is Yes.
 Otherwise, the output is No.
Program
#include <iostream>
#include <vector>
using namespace std;
// Sieve of Eratosthenes algorithm.
void SieveOfEratosthenes(int N, vector<bool> &isPrime)
{
// Initialize 0 and 1 as nonprime for the time being although we know, they are neither prime, nor composite.
isPrime[0] = false;
isPrime[1] = false;
for (int p = 2; p * p <= N; p++)
{
// If p is not yet divided by any number before, it is a prime and updates all its multiples till ‘N’ as composite.
if (isPrime[p] == true)
{
// Update all multiples of p.
for (int i = p * 2; i <= N; i += p)
isPrime[i] = false;
}
}
}
// To find any such representation as mentioned in the problem statement.
bool isRepresentable(int N)
{
// Mark all numbers as primes initially.
vector<bool> isPrime(1, N + 1);
// Update the status of the numbers till N.
SieveOfEratosthenes(N, isPrime);
// Traversing through the array.
for (int i = 2; i < N; i++)
{
if (N % i == 0)
{
if (isPrime[i] && !isPrime[N / i])
return true;
else if (isPrime[N / i] && !isPrime[i])
return true;
}
}
return false;
}
// Driver Code
int main()
{
int N;
cin >> N;
if (isRepresentable(N))
{
cout << "Yes";
}
else
{
cout << "No";
}
return 0;
}
Input
6
Output
No
Time Complexity
The time complexity of the above approach is O(N * log(log(N))), where ‘N’ is the input number.
It is because the time complexity of Sieve of Eratosthenes is O(N * log( logN )) and we are running a for loop till ‘N’. So, overall time complexity becomes O(N + N * log(log(N))) = O(N * log(log(N))).
Space Complexity
The space complexity of the above approach is O(N), where ‘N’ is the input number.
It is because we are creating a boolean array of size ‘N’ to identify numbers till ‘N’ as being prime or composite.
Key Takeaways
This blog discussed a puzzling coding question involving the Sieve of Eratosthenes. Sieve of Eratosthenes is a wellknown factorization technique frequently asked in programming contests and technical interviews. It is wellknown for its efficient time complexity to identify all prime numbers up to a given number. Several standard problems can be solved efficiently using the Sieve of Eratosthenes.
Hence learning never stops, and there is a lot more to learn.
So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!