Dado un número X y una array de N números. La tarea es imprimir todos los números en la array cuyo conjunto de factores primos es un subconjunto del conjunto de factores primos de X.
Ejemplos:
Entrada: X = 60, a[] = {2, 5, 10, 7, 17}
Salida: 2 5 10
Conjunto de factores primos de 60: {2, 3, 5}
Conjunto de factores primos de 2: {2}
Conjunto de factores primos de 5: {5}
Conjunto de factores primos de 10: {2, 5}
Conjunto de factores primos de 7: {7}
Conjunto de factores primos de 17: {17}
Por lo tanto, solo 2, 5 y conjunto de 10 de factores primos es un subconjunto del conjunto de
factores primos de 60.
Entrada: X = 15, a[] = {2, 8}
Salida: No existen tales números
Enfoque : iterar para cada elemento de la array y seguir dividiendo el número por el mcd del número y X hasta que mcd se convierta en 1 para el número y X. Si al final el número se convierte en 1 después de la división continua, imprima ese número.
A continuación se muestra la implementación del enfoque anterior:
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
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
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.
?>
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>
Producción:
2 5 10
Complejidad de tiempo: O(n logn), donde n es el tiempo para recorrer un tamaño de array dado y operaciones de registro para la función gcd que va dentro de él
Espacio auxiliar: O(1), no se requiere espacio adicional