Given a number X and an array of N numbers. The task is to print all the numbers in the array whose set of prime factors is a subset of the set of the prime factors of X.
Examples:
Input: X = 60, a[] = {2, 5, 10, 7, 17}
Output: 2 5 10
Set of prime factors of 60: {2, 3, 5}
Set of prime factors of 2: {2}
Set of prime factors of 5: {5}
Set of prime factors of 10: {2, 5}
Set of prime factors of 7: {7}
Set of prime factors of 17: {17}
Hence only 2, 5 and 10’s set of prime factors is a subset of set of prime
factors of 60.
Input: X = 15, a[] = {2, 8}
Output: There are no such numbers
Approach: Iterate for every element in the array, and keep dividing the number by the gcd of the number and X till gcd becomes 1 for the number and X. If at the end the number becomes 1 after continuous division, then print that number.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to print all the numbersvoid printNumbers(int a[], int n, int x){ bool flag = false; // Iterate for every element in the array for (int i = 0; i < n; i++) { int num = a[i]; // Find the gcd int g = __gcd(num, x); // Iterate till gcd is 1 // of number and x while (g != 1) { // Divide the number by gcd num /= g; // Find the new gcdg g = __gcd(num, x); } // If the number is 1 at the end // then print the number if (num == 1) { flag = true; cout << a[i] << " "; } } // If no numbers have been there if (!flag) cout << "There are no such numbers";}// Drivers codeint main(){ int x = 60; int a[] = { 2, 5, 10, 7, 17 }; int n = sizeof(a) / sizeof(a[0]); printNumbers(a, n, x); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;public class GFG{// Function to print all the numbersstatic void printNumbers(int a[], int n, int x){ boolean flag = false; // Iterate for every element in the array for (int i = 0; i < n; i++) { int num = a[i]; // Find the gcd int g = __gcd(num, x); // Iterate till gcd is 1 // of number and x while (g != 1) { // Divide the number by gcd num /= g; // Find the new gcdg g = __gcd(num, x); } // If the number is 1 at the end // then print the number if (num == 1) { flag = true; System.out.print(a[i] + " "); } } // If no numbers have been there if (!flag) System.out.println("There are no such numbers");}static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); }// Drivers codepublic static void main(String[] args){ int x = 60; int a[] = { 2, 5, 10, 7, 17 }; int n = a.length; printNumbers(a, n, x);}}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 program to implement # the above approach from math import gcd# Function to print all the numbers def printNumbers(a, n, x) : flag = False # Iterate for every element in the array for i in range(n) : num = a[i] # Find the gcd g = gcd(num, x) # Iterate till gcd is 1 # of number and x while (g != 1) : # Divide the number by gcd num //= g # Find the new gcdg g = gcd(num, x) # If the number is 1 at the end # then print the number if (num == 1) : flag = True; print(a[i], end = " "); # If no numbers have been there if (not flag) : print("There are no such numbers") # Driver Code if __name__ == "__main__" : x = 60 a = [ 2, 5, 10, 7, 17 ] n = len(a) printNumbers(a, n, x) # This code is contributed by Ryuga |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to print all the numbersstatic void printNumbers(int []a, int n, int x){ bool flag = false; // Iterate for every element in the array for (int i = 0; i < n; i++) { int num = a[i]; // Find the gcd int g = __gcd(num, x); // Iterate till gcd is 1 // of number and x while (g != 1) { // Divide the number by gcd num /= g; // Find the new gcdg g = __gcd(num, x); } // If the number is 1 at the end // then print the number if (num == 1) { flag = true; Console.Write(a[i] + " "); } } // If no numbers have been there if (!flag) Console.WriteLine("There are no such numbers");}static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); }// Driver codepublic static void Main(String[] args){ int x = 60; int []a = { 2, 5, 10, 7, 17 }; int n = a.Length; printNumbers(a, n, x);}}// This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript program to implement// the above approach// Function to print all the numbers// Find the gcdfunction __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b); }function printNumbers(a, n, x){ let flag = false; // Iterate for every element in the array for (let i = 0; i < n; i++) { let num = a[i]; // Find the gcd let g = __gcd(num, x); // Iterate till gcd is 1 // of number and x while (g != 1) { // Divide the number by gcd num = parseInt(num/g); // Find the new gcdg g = __gcd(num, x); } // If the number is 1 at the end // then print the number if (num == 1) { flag = true; document.write(a[i] + " "); } } // If no numbers have been there if (!flag) document.write("There are no such numbers");}// Drivers code let x = 60; let a = [ 2, 5, 10, 7, 17 ]; let n = a.length; printNumbers(a, n, x);</script> |
PHP
<?php// PHP program to implement// the above approach// Function to print all the numbersfunction printNumbers($a, $n, $x){ $flag = false; // Iterate for every element in the array for ($i = 0; $i < $n; $i++) { $num = $a[$i]; // Find the gcd $g = __gcd($num, $x); // Iterate till gcd is 1 // of number and x while ($g != 1) { // Divide the number by gcd $num /= $g; // Find the new gcdg $g = __gcd($num, $x); } // If the number is 1 at the end // then print the number if ($num == 1) { $flag = true; echo $a[$i] , " "; } } // If no numbers have been there if (!$flag) echo ("There are no such numbers");}function __gcd($a, $b) { if ($b == 0) return $a; return __gcd($b, $a % $b); }// Driver code$x = 60;$a = array(2, 5, 10, 7, 17 );$n = count($a);printNumbers($a, $n, $x);// This code has been contributed by ajit.?> |
Output
2 5 10
Time Complexity: O(n logn), where n is the time to traverse a given array size and logn operations for gcd function going inside it
Auxiliary Space: O(1), no extra space required
Another Approach Using DP :
To solve this problem using dynamic programming (DP), we can use a boolean table dp[i][j], where dp[i][j] will be true if there is a subset of elements from the first i elements of the array (a[0] to a[i-1]) whose gcd is j.
We can fill this table in a bottom-up manner, starting from dp[0][j] = (j == 1) for all j, because an empty subset will have a gcd of 1. Then, for each i > 0 and j > 0, we can compute dp[i][j] by considering two cases:
- We don’t include a[i-1] in the subset: In this case, dp[i][j] will be the same as dp[i-1][j], because we are not adding a[i-1] to the subset.
- We include a[i-1] in the subset: In this case, dp[i][j] will be true if dp[i-1][j] is true (because we can already form a subset whose gcd is j without using a[i-1]), or if dp[i-1][gcd(j, a[i-1])] is true (because we can form a subset whose gcd is j by adding a[i-1] to a subset whose gcd is gcd(j, a[i-1])).
After filling this table, we can simply iterate over the last row (dp[n][j]) and print out all the j such that dp[n][j] is true.
C++
#include <bits/stdc++.h>using namespace std;void printNumbers(int a[], int n, int x){ bool flag = false; // Iterate for every element in the array for (int i = 0; i < n; i++) { int num = a[i]; // Find the gcd int g = __gcd(num, x); // Iterate till gcd is 1 of number and x while (g != 1) { // Divide the number by gcd num /= g; // Find the new gcd g = __gcd(num, x); } // If the number is 1 at the end, then print the number if (num == 1) { flag = true; cout << a[i] << " "; } } // If no numbers have been printed, print "There are no such numbers" if (!flag) cout << "There are no such numbers";}int main(){ int x = 60; int a[] = { 2, 5, 10, 7, 17 }; int n = sizeof(a) / sizeof(a[0]); printNumbers(a, n, x); return 0;} |
Java
import java.util.Arrays;public class GFG { // Function to find the greatest common divisor (GCD) of // two numbers public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to print numbers whose GCD with x is 1 public static void printNumbers(int[] arr, int x) { boolean flag = false; // Iterate over every element in the array for (int i = 0; i < arr.length; i++) { int num = arr[i]; // Find the GCD int g = gcd(num, x); // Iterate until GCD is 1 of number and x while (g != 1) { // Divide the number by GCD num /= g; // Find the new GCD g = gcd(num, x); } // If the number is 1 at the end, then print the number if (num == 1) { flag = true; System.out.print(arr[i] + " "); } } // If no numbers have been printed, print // "There are no such numbers" if (!flag) System.out.print("There are no such numbers"); } public static void main(String[] args) { int x = 60; int[] arr = { 2, 5, 10, 7, 17 }; printNumbers(arr, x); // This code is contributed by Shivam Tiwari }} |
Python3
from math import gcddef printNumbers(arr, x): flag = False # Iterate for every element in the array for i in range(len(arr)): num = arr[i] # Find the gcd g = gcd(num, x) # Iterate till gcd is 1 of number and x while g != 1: # Divide the number by gcd num //= g # Find the new gcd g = gcd(num, x) # If the number is 1 at the end, then print the number if num == 1: flag = True print(arr[i], end=" ") # If no numbers have been printed, print #"There are no such numbers" if not flag: print("There are no such numbers")# Driver Codeif __name__ == "__main__": x = 60 arr = [2, 5, 10, 7, 17] printNumbers(arr, x)# This code is contributed by Shivam Tiwari |
C#
using System;public class Program{ public static void PrintNumbers(int[] arr, int x) { bool flag = false; // Iterate for every element in the array for (int i = 0; i < arr.Length; i++) { int num = arr[i]; // Find the gcd int g = GCD(num, x); // Iterate till gcd is 1 of number and x while (g != 1) { // Divide the number by gcd num /= g; // Find the new gcd g = GCD(num, x); } // If the number is 1 at the end, then print the number if (num == 1) { flag = true; Console.Write(arr[i] + " "); } } // If no numbers have been printed, // print "There are no such numbers" if (!flag) Console.Write("There are no such numbers"); } public static int GCD(int a, int b) { if (b == 0) return a; return GCD(b, a % b); } public static void Main() { int x = 60; int[] arr = { 2, 5, 10, 7, 17 }; PrintNumbers(arr, x); // This code is contributed by Shivam Tiwari }} |
Javascript
// Function to find and print numbers from the array with GCD equal to 1 with xfunction printNumbers(a, n, x) { let flag = false; // Iterate for every element in the array for (let i = 0; i < n; i++) { let num = a[i]; // Find the gcd using a helper function gcd(a, b) let g = gcd(num, x); // Iterate till gcd is 1 of number and x while (g !== 1) { // Divide the number by gcd num /= g; // Find the new gcd g = gcd(num, x); } // If the number is 1 at the end, then print the number if (num === 1) { flag = true; console.log(a[i] + " "); } } // If no numbers have been printed, print "There are no such numbers" if (!flag) { console.log("There are no such numbers"); }}// Helper function to find the greatest common divisor (GCD) using the Euclidean algorithmfunction gcd(a, b) { if (b === 0) { return a; } return gcd(b, a % b);}// Main codeconst x = 60;const a = [2, 5, 10, 7, 17];const n = a.length;printNumbers(a, n, x); |
Output
2 5 10
Time Complexity: O(n logn)
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!
