Dada una array de números 
y el valor de 
, verifica si cada número 
se puede expresar como el producto de números primos exactos. Para cada elemento de la array, imprima ‘SÍ’ si se cumple la condición, de lo contrario, imprima ‘NO’.
Nota: También se pueden considerar números primos repetidos. Por ejemplo, si k = 2, entonces n = 4 (=2*2) es una entrada válida.
Consideremos el número 36. 36 se puede factorizar como 2*2*3*3. Por lo tanto, es el producto de 4 números primos. Si el valor de k es 4, entonces la salida debe ser SÍ . Para otros valores de k, la salida debe ser NO .
Más ejemplos:
Input: arr[] = {30, 8, 12}, K = 3
Output: YES, YES, YES
30 = 2*3*5
8 = 2*2*2
12 = 2*3*2
Input: arr[] = {30, 16, 32}, k = 5
Output: NO, NO, YES
Only 32 can be represented as product of
5 prime numbers.
En este artículo, comprobaremos si los números dados se pueden expresar como el producto de exactamente k números primos. El concepto subyacente que estaremos usando es simplemente una variación del Tamiz de Eratóstenes .
Recomendado: Cómo construir el Tamiz de Eratóstenes
Diferencia clave: en el tamiz, en lugar de almacenar valores binarios (0 si el número no es primo, 1 si el número es primo), podemos almacenar cuántos factores primos (repetitivos) componen ese número. Esta modificación se realiza durante su construcción.
El procedimiento generalizado para crear este tamiz modificado es el siguiente:
- Cree una array llena de 0 para almacenar la lista de enteros consecutivos (2, 3, 4… 10^6).
- Deje que el valor de i se establezca en 2 inicialmente. Este es nuestro primer número primo.
- Recorra todos los múltiplos de i (2*i, 3*i… hasta 10^6) almacenando su valor como j. Continúe con los pasos 3 y 4.
- Calcule el número de veces que j se puede factorizar usando i y almacene el resultado en la variable conteo.
- Cuando el número j no se puede factorizar más usando i, incremente el valor de Sieve[j] por el valor de conteo.
- Finalmente, encuentre el siguiente número primo mayor que i en la lista de enteros. Si no hay tal número, termine el proceso. De lo contrario, siga desde el paso 2 nuevamente.
Explicación con ejemplo:
PASO 1:
La array de tamices vacía inicializada se ve como se ilustra a continuación. En aras de la simplicidad, concentrémonos solo en los índices 2 a 12. Los valores almacenados inicialmente son 0 para todos los índices.
Ahora, el primer número primo que tomaremos es 2. Este es el valor de i.
PASO 2:
Inicialice la variable j para que contenga el valor de cada múltiplo subsiguiente de i a partir de 2*i, que en este caso es 4.
PASO 3:
El tercer paso implica el cálculo de la descomposición en factores primos de j. Más específicamente, solo estamos interesados en contar el número de ocurrencias de i cuando factorizas j.
El procedimiento de cálculo es simple. Simplemente divide el valor de j con i hasta obtener un número que no sea divisible por i. Aquí, 4 se puede dividir por 2 dos veces. 4/2 da 2 y 2/2 da 1, que no es divisible por 2 y el ciclo se detiene. Por lo tanto, actualizamos el valor de Sieve[4] con el valor de la variable de conteo, que es 2.
PASO 4:
Podemos proceder con los otros elementos de manera similar. Luego, el valor de j es 6. 6 solo se puede dividir por 2 una vez. Por lo tanto, el valor de Sieve[6] es 1.
La array Sieve calculada final debería verse así. Tenga en cuenta que cualquier índice que almacene el valor 0 representa un número que no es el producto de 2 o más números primos. Esto incluye todos los números primos, 0 y 1.
La segunda cosa a tener en cuenta es que solo necesitamos verificar
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if each element of
// the given array is a product of exactly
// K prime factors
#include <iostream>
#define MAX 1000000
using namespace std;
// initialise the global sieve array
int Sieve[MAX] = { 0 };
// Function to generate Sieve
void constructSieve()
{
// NOTE: k value is necessarily more than 1
// hence, 0, 1 and any prime number cannot be
// represented as product of
// two or more prime numbers
for (int i = 2; i <= MAX; i++) {
if (Sieve[i] == 0) {
for (int j = 2 * i; j <= MAX; j += i) {
int temp = j;
while (temp > 1 && temp % i == 0) {
Sieve[j]++;
temp = temp / i;
}
}
}
}
}
// Function to check if each number of array
// satisfies the given condition
void checkElements(int A[], int n, int k)
{
for (int i = 0; i < n; i++) {
if (Sieve[A[i]] == k) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
}
// Driver Code
int main()
{
// first construct the sieve
constructSieve();
int k = 3;
int A[] = { 12, 36, 42, 72 };
int n = sizeof(A) / sizeof(int);
checkElements(A, n, k);
return 0;
}
Java
// Java program to check if each element of
// the given array is a product of exactly
// K prime factors
import java.util.*;
class GFG
{
static int MAX = 1000000;
// initialise the global sieve array
static int[] Sieve = new int[MAX+1];
// Function to generate Sieve
static void constructSieve()
{
// NOTE: k value is necessarily more than 1
// hence, 0, 1 and any prime number cannot be
// represented as product of
// two or more prime numbers
for (int i = 2; i <= MAX; i++)
{
if (Sieve[i] == 0)
{
for (int j = 2 * i; j <= MAX; j += i)
{
int temp = j;
while (temp > 1 && temp % i == 0)
{
Sieve[j]++;
temp = temp / i;
}
}
}
}
}
// Function to check if each number of array
// satisfies the given condition
static void checkElements(int A[], int n, int k)
{
for (int i = 0; i < n; i++)
{
if (Sieve[A[i]] == k)
{
System.out.println("YES");
}
else
{
System.out.println("No");
}
}
}
// Driver Code
public static void main(String[] args)
{
// first construct the sieve
constructSieve();
int k = 3;
int A[] = {12, 36, 42, 72};
int n = A.length;
checkElements(A, n, k);
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program to check if each element of
# the given array is a product of exactly
# K prime factors
MAX = 1000000
# initialise the global sieve array
Sieve = [0]*(MAX + 1)
# Function to generate Sieve
def constructSieve() :
# NOTE: k value is necessarily more than 1
# hence, 0, 1 and any prime number cannot be
# represented as product of
# two or more prime numbers
for i in range(2, MAX + 1) :
if (Sieve[i] == 0) :
for j in range(2*i, MAX + 1, i) :
temp = j;
while (temp > 1 and temp % i == 0) :
Sieve[j] += 1;
temp = temp // i;
# Function to check if each number of array
# satisfies the given condition
def checkElements(A, n, k) :
for i in range(n) :
if (Sieve[A[i]] == k) :
print("YES");
else :
print("NO");
# Driver Code
if __name__ == "__main__" :
# first construct the sieve
constructSieve();
k = 3;
A = [ 12, 36, 42, 72 ];
n = len(A);
checkElements(A, n, k);
# This code is contributed by AnkitRai01
C#
// C# program to check if each element of
// the given array is a product of exactly
// K prime factors
using System;
class GFG
{
static int MAX = 1000000;
// initialise the global sieve array
static int[] Sieve = new int[MAX+1];
// Function to generate Sieve
static void constructSieve()
{
// NOTE: k value is necessarily more than 1
// hence, 0, 1 and any prime number cannot be
// represented as product of
// two or more prime numbers
for (int i = 2; i <= MAX; i++)
{
if (Sieve[i] == 0)
{
for (int j = 2 * i; j <= MAX; j += i)
{
int temp = j;
while (temp > 1 && temp % i == 0)
{
Sieve[j]++;
temp = temp / i;
}
}
}
}
}
// Function to check if each number of array
// satisfies the given condition
static void checkElements(int []A, int n, int k)
{
for (int i = 0; i < n; i++)
{
if (Sieve[A[i]] == k)
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("No");
}
}
}
// Driver Code
public static void Main()
{
// first construct the sieve
constructSieve();
int k = 3;
int []A = {12, 36, 42, 72};
int n = A.Length;
checkElements(A, n, k);
}
}
// This code contributed by anuj_67...
Javascript
<script>
// Javascript program to check if each element of
// the given array is a product of exactly
// K prime factors
const MAX = 1000000;
// initialise the global sieve array
let Sieve = new Array(MAX).fill(0);
// Function to generate Sieve
function constructSieve()
{
// NOTE: k value is necessarily more than 1
// hence, 0, 1 and any prime number cannot be
// represented as product of
// two or more prime numbers
for (let i = 2; i <= MAX; i++) {
if (Sieve[i] == 0) {
for (let j = 2 * i; j <= MAX; j += i)
{
let temp = j;
while (temp > 1 && temp % i == 0)
{
Sieve[j]++;
temp = parseInt(temp / i);
}
}
}
}
}
// Function to check if each number of array
// satisfies the given condition
function checkElements(A, n, k)
{
for (let i = 0; i < n; i++) {
if (Sieve[A[i]] == k) {
document.write("YES<br>");
}
else {
document.write("NO<br>");
}
}
}
// Driver Code
// first construct the sieve
constructSieve();
let k = 3;
let A = [ 12, 36, 42, 72 ];
let n = A.length;
checkElements(A, n, k);
</script>
YES NO YES NO
Complejidad de tiempo: O(n*log(logn)), donde n es la longitud de la array A.
Complejidad de espacio : O(MAX), donde MAX es 10 6 .