Given a number N, the task is to check if N can be represented as the product of a prime and a composite number or not. If it can, then print Yes, otherwise No.
Examples:
Input: N = 52
Output: Yes
Explanation: 52 can be represented as the multiplication of 4 and 13, where 4 is a composite and 13 is a prime number.Input: N = 49
Output: No
Approach: This problem can be solved with the help of the Sieve of Eratosthenes algorithm. Now, to solve this problem, follow the below steps:
- Create a boolean array isPrime, where the ith element is true if it is a prime, otherwise it’s false.
- Find all prime numbers till N using sieve algorithm.
- Now run a loop for i=2 to i<N, and on each iteration:
- Check for these two conditions:
- If N is divisible by i.
- If i is a prime number and N/i isn’t or if i isn’t a prime number and N/i is.
- If both of the above conditions satisfy, return true.
- Otherwise, return false.
- Check for these two conditions:
- Print the answer, according to the above observation.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to generate all prime// numbers less than Nvoid SieveOfEratosthenes(int N, bool isPrime[]){ // Initialize all entries of boolean array // as true. A value in isPrime[i] will finally // be false if i is Not a prime, else true // bool isPrime[N+1]; isPrime[0] = isPrime[1] = false; for (int i = 2; i <= N; i++) isPrime[i] = true; for (int p = 2; p * p <= N; p++) { // If isPrime[p] is not changed, // then it is a prime if (isPrime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= N; i += p) isPrime[i] = false; } }}// Function to check if we can// represent N as product of a prime// and a composite number or notbool isRepresentable(int N){ // Generating primes using Sieve bool isPrime[N + 1]; SieveOfEratosthenes(N, isPrime); // Traversing through the array for (int i = 2; i < N; i++) { if (N % i == 0) { if (N % i == 0 and (isPrime[i] and !isPrime[N / i]) or (!isPrime[i] and isPrime[N / i])) { return true; } } } return false;}// Driver Codeint main(){ int N = 52; if (isRepresentable(N)) { cout << "Yes"; } else { cout << "No"; } return 0;} |
Java
// Java program to implement the above approachimport java.util.*;public class GFG{ // Function to generate all prime// numbers less than Nstatic void SieveOfEratosthenes(int N, boolean []isPrime){ // Initialize all entries of boolean array // as true. A value in isPrime[i] will finally // be false if i is Not a prime, else true // bool isPrime[N+1]; isPrime[0] = isPrime[1] = false; for (int i = 2; i <= N; i++) isPrime[i] = true; for (int p = 2; p * p <= N; p++) { // If isPrime[p] is not changed, // then it is a prime if (isPrime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= N; i += p) isPrime[i] = false; } }}// Function to check if we can// represent N as product of a prime// and a composite number or notstatic boolean isRepresentable(int N){ // Generating primes using Sieve boolean []isPrime = new boolean[N + 1]; SieveOfEratosthenes(N, isPrime); // Traversing through the array for (int i = 2; i < N; i++) { if (N % i == 0) { if (N % i == 0 && (isPrime[i] && !isPrime[N / i]) || (!isPrime[i] && isPrime[N / i])) { return true; } } } return false;}// Driver Codepublic static void main(String arg[]){ int N = 52; if (isRepresentable(N)) { System.out.println("Yes"); } else { System.out.println("No"); }}}// This code is contributed by Samim Hossain Mondal. |
Python3
# python program for the above approachimport math# Function to generate all prime# numbers less than Ndef SieveOfEratosthenes(N, isPrime): # Initialize all entries of boolean array # as true. A value in isPrime[i] will finally # be false if i is Not a prime, else true # bool isPrime[N+1]; isPrime[0] = False isPrime[1] = False for i in range(2, N+1): isPrime[i] = True for p in range(2, int(math.sqrt(N)) + 1): # If isPrime[p] is not changed, # then it is a prime if (isPrime[p] == True): # Update all multiples of p for i in range(p+2, N+1, p): isPrime[i] = False# Function to check if we can# represent N as product of a prime# and a composite number or notdef isRepresentable(N): # Generating primes using Sieve isPrime = [0 for _ in range(N + 1)] SieveOfEratosthenes(N, isPrime) # Traversing through the array for i in range(2, N): if (N % i == 0): if (N % i == 0 and (isPrime[i] and not isPrime[N // i]) or (not isPrime[i] and isPrime[N // i])): return True return False# Driver Codeif __name__ == "__main__": N = 52 if (isRepresentable(N)): print("Yes") else: print("No") # This code is contributed by rakeshsahni |
C#
// C# program to implement the above approachusing System;class GFG{// Function to generate all prime// numbers less than Nstatic void SieveOfEratosthenes(int N, bool []isPrime){ // Initialize all entries of boolean array // as true. A value in isPrime[i] will finally // be false if i is Not a prime, else true // bool isPrime[N+1]; isPrime[0] = isPrime[1] = false; for (int i = 2; i <= N; i++) isPrime[i] = true; for (int p = 2; p * p <= N; p++) { // If isPrime[p] is not changed, // then it is a prime if (isPrime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= N; i += p) isPrime[i] = false; } }}// Function to check if we can// represent N as product of a prime// and a composite number or notstatic bool isRepresentable(int N){ // Generating primes using Sieve bool []isPrime = new bool[N + 1]; SieveOfEratosthenes(N, isPrime); // Traversing through the array for (int i = 2; i < N; i++) { if (N % i == 0) { if (N % i == 0 && (isPrime[i] && !isPrime[N / i]) || (!isPrime[i] && isPrime[N / i])) { return true; } } } return false;}// Driver Codepublic static void Main(){ int N = 52; if (isRepresentable(N)) { Console.Write("Yes"); } else { Console.Write("No"); }}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript program for the above approach// Function to generate all prime// numbers less than Nfunction SieveOfEratosthenes(N, isPrime){ // Initialize all entries of boolean array // as true. A value in isPrime[i] will finally // be false if i is Not a prime, else true // bool isPrime[N+1]; isPrime[0] = isPrime[1] = false; for (let i = 2; i <= N; i++) isPrime[i] = true; for (let p = 2; p * p <= N; p++) { // If isPrime[p] is not changed, // then it is a prime if (isPrime[p] == true) { // Update all multiples of p for (let i = p * 2; i <= N; i += p) isPrime[i] = false; } }}// Function to check if we can// represent N as product of a prime// and a composite number or notfunction isRepresentable(N){ // Generating primes using Sieve let isPrime = []; SieveOfEratosthenes(N, isPrime); // Traversing through the array for (let i = 2; i < N; i++) { if (N % i == 0) { if (N % i == 0 && (isPrime[i] && !isPrime[N / i]) || (!isPrime[i] && isPrime[N / i])) { return true; } } } return false;}// Driver Codelet N = 52;if (isRepresentable(N)) { document.write("Yes");}else { document.write("No");}// This code is contributed by Samim Hossain Mondal.</script> |
Output
Yes
Time complexity: O(N*log(logN))
Auxiliary Space: O(N)
Another Approach
Below is the implementation of the above approach:
C++
#include <iostream>#include <cmath>// Function to check if a number is primebool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true;}// Function to check if N can be represented as the product of a prime and a composite numberbool isProductOfPrimeAndComposite(int N) { if (N <= 3) return false; for (int i = 2; i <= sqrt(N); i++) { if (N % i == 0) { int factor1 = i; int factor2 = N / i; // Check if both factors are prime and composite numbers if (isPrime(factor1) && !isPrime(factor2)) return true; if (!isPrime(factor1) && isPrime(factor2)) return true; } } return false;}// Driver Codeint main() { int N=52; if (isProductOfPrimeAndComposite(N)) std::cout << "Yes" << std::endl; else std::cout << "No" << std::endl; return 0;} |
Java
import java.util.*;public class GFG { // Function to check if a number is prime static boolean isPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return false; } return true; } // Function to check if N can be represented as the product // of a prime and a composite number static boolean isProductOfPrimeAndComposite(int N) { if (N <= 3) return false; for (int i = 2; i <= Math.sqrt(N); i++) { if (N % i == 0) { int factor1 = i; int factor2 = N / i; // Check if both factors are prime and composite numbers if (isPrime(factor1) && !isPrime(factor2)) return true; if (!isPrime(factor1) && isPrime(factor2)) return true; } } return false; } // Driver Code public static void main(String[] args) { int N = 52; if (isProductOfPrimeAndComposite(N)) System.out.println("Yes"); else System.out.println("No"); // This Code Is Contributed By Shubham Tiwari. }} |
Python3
import math# Function to check if a number is primedef is_prime(n): if n <= 1: return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True# Function to check if N can be represented as the # product of a prime and a composite numberdef is_product_of_prime_and_composite(N): if N <= 3: return False for i in range(2, int(math.sqrt(N)) + 1): if N % i == 0: factor1 = i factor2 = N // i # Check if both factors are prime and composite numbers if is_prime(factor1) and not is_prime(factor2): return True if not is_prime(factor1) and is_prime(factor2): return True return False# Driver Codeif __name__ == "__main__": N = 52 if is_product_of_prime_and_composite(N): print("Yes") else: print("No") # This Code Is Contributed By Shubham Tiwari. |
C#
using System;class GFG{ // Function to check if a number is prime static bool IsPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) return false; } return true; } // Function to check if N can be represented as the // product of a prime and a composite number static bool IsProductOfPrimeAndComposite(int N) { if (N <= 3) return false; for (int i = 2; i <= Math.Sqrt(N); i++) { if (N % i == 0) { int factor1 = i; int factor2 = N / i; // Check if both factors are prime and // composite numbers if (IsPrime(factor1) && !IsPrime(factor2)) return true; if (!IsPrime(factor1) && IsPrime(factor2)) return true; } } return false; } static void Main(string[] args) { int N = 52; if (IsProductOfPrimeAndComposite(N)) Console.WriteLine("Yes"); else Console.WriteLine("No"); // This Code Is Contributed By Shubham Tiwari. }} |
Javascript
// Function to check if a number is primefunction isPrime(n) { // If the number is less than or equal to 1, it is not prime if (n <= 1) return false; // Check divisibility from 2 up to the square root of the number for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) // If the number is divisible by any number in this range, it is not prime return false; } // If the number is not divisible by any number in the range, it is prime return true;}// Function to check if N can be represented as the product of a prime and a composite numberfunction isProductOfPrimeAndComposite(N) { // If N is less than or equal to 3, it cannot be represented as the product of a prime and a composite number if (N <= 3) return false; // Check for factors from 2 up to the square root of N for (let i = 2; i <= Math.sqrt(N); i++) { if (N % i === 0) { let factor1 = i; let factor2 = N / i; // If one factor is prime and the other is composite, return true if (isPrime(factor1) && !isPrime(factor2)) return true; if (!isPrime(factor1) && isPrime(factor2)) return true; } } // If no such factors are found, return false return false;}// Test the function with an examplelet N = 52;if (isProductOfPrimeAndComposite(N)) console.log("Yes");else console.log("No");// This Code Is Contributed By Shubham Tiwari. |
Output
Yes
Time Complexity: O(sqrt(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
