Check if a Number can be Expressed as Product of a Prime and a Composite Number

Approach 1

We will use a brute-force approach to solve this problem. Identify all the factors of the given number and check each pair if they satisfy the given criteria.

Algorithm

1. Take the input number 'N'.
2. Run a loop till sqrt(N) with variable X and do the following:
   1. If ‘N’ is not divisible by ‘X’, continue.
   2. Check if one of ‘X’ and ‘N/X’ is prime and the other one is composite.
   3. If the above condition is true, output Yes and return.
3. 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:

1. 'X' divides 'N' and is a prime.
2. 'N/X' is a composite number.

Algorithm

1. Take the input number 'N'.
2. Run the Sieve of Eratosthenes algorithm to identify all prime numbers up to 'N' and store them in a boolean array 'IS_PRIME.'
3. Run a for loop with variable 'X' till 'N' - 1 and check for the following:
   1. If 'X' divides 'N':
      1. Check if 'IS_PRIME[X]' is true and 'IS_PRIME[N/X]' is false.
      2. Else if 'IS_PRIME[n/X]' is true and 'IS_PRIME[X]' is false.
      3. If any of the above conditions is true, the answer is Yes.
4. 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 non-prime 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 well-known factorization technique frequently asked in programming contests and technical interviews. It is well-known 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!