Print all numbers whose set of prime factors is a subset of the set of the prime factors of X

0 0 10 minutes read

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 numbers
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;
            cout << a[i] << " ";
        }
    }
 
    // If no numbers have been there
    if (!flag)
        cout << "There are no such numbers";
}
 
// Drivers code
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

// Java program to implement
// the above approach
import java.io.*;
public class GFG
{
 
// Function to print all the numbers
static 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 code
public 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 approach
using System;
 
class GFG
{
 
// Function to print all the numbers
static 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 code
public 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 gcd
function __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 numbers
function 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 gcd
 
def 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 Code
if __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 x
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 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 algorithm
function gcd(a, b) {
    if (b === 0) {
        return a;
    }
    return gcd(b, a % b);
}
 
// Main code
const 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 zambiatek!