Dado un número entero N , la tarea es verificar si se puede expresar como un producto de exactamente K divisores primos.
Ejemplos:
Input: N = 12, K = 3 Output: Yes Explanation: 12 can be expressed as product of 2×2×3. Input: N = 14, K = 3 Output: No Explanation: 14 can be only expressed as product of 2×7.
Enfoque:
Para resolver el problema mencionado anteriormente, se nos da el valor N y encontraremos el número máximo de valores en los que podemos dividir N. Podemos representar la descomposición en factores primos de N como 
donde p i son los factores primos de N y a i son los exponentes. Sabemos que el número total de divisores de N es 
. Por tanto, podemos observar que tenemos que comprobar si es posible representar N como producto de K números o no. Si la división máxima es menor que K, entonces no es posible expresarlo exactamente en K divisores primos, de lo contrario, siempre es posible.
C++
// CPP implementation to Check if a
// number can be expressed as a
// product of exactly K prime divisors
#include <bits/stdc++.h>
using namespace std;
// function to find K prime divisors
void KPrimeDivisors(int N, int K)
{
int maximum_split = 0;
// count number of 2s that divide N
while (N % 2 == 0) {
maximum_split++;
N /= 2;
}
// N must be odd at this point.
// So we can skip one element
for (int i = 3; i * i <= N; i = i + 2) {
while (N % i == 0) {
// divide the value of N
N = N / i;
// increment count
maximum_split++;
}
}
// Condition to handle the case when n
// is a prime number greater than 2
if (N > 2)
maximum_split++;
// check if maximum_split is less than K
// then it not possible
if (maximum_split < K) {
printf("No\n");
return;
}
printf("Yes\n");
}
/* Driver code */
int main()
{
// initialise N and K
int N = 12;
int K = 3;
KPrimeDivisors(N, K);
return 0;
}
Java
// Java implementation to Check if a
// number can be expressed as a
// product of exactly K prime divisors
class GFG {
// function to find K prime divisors
static void KPrimeDivisors(int N, int K)
{
int maximum_split = 0;
// count number of 2s that divide N
while (N % 2 == 0) {
maximum_split++;
N /= 2;
}
// N must be odd at this point.
// So we can skip one element
for (int i = 3; i * i <= N; i = i + 2) {
while (N % i == 0) {
// divide the value of N
N = N / i;
// increment count
maximum_split++;
}
}
// Condition to handle the case when n
// is a prime number greater than 2
if (N > 2)
maximum_split++;
// check if maximum_split is less than K
// then it not possible
if (maximum_split < K) {
System.out.println("No");
return;
}
System.out.println("Yes");
}
/* Driver code */
public static void main (String[] args)
{
// initialise N and K
int N = 12;
int K = 3;
KPrimeDivisors(N, K);
}
}
// This code is contributed by Yash_R
Python3
# Python implementation to Check if a
# number can be expressed as a
# product of exactly K prime divisors
import math as mt
# function to find K prime divisors
def KPrimeDivisors(n, k):
# To count maximum split of N
maximum_split = 0
# count number of 2s that divide N
while n % 2 == 0:
maximum_split+= 1
n = n // 2
# n must be odd at this point
# so we skip one element
for i in range(3, mt.ceil(mt.sqrt(n)), 2):
while n % i == 0:
n = n / i;
maximum_split+= 1
# Condition to handle the case when n
# is a prime number greater than 2
if n > 2:
maximum_split+= 1
# check if maximum_split is less than K
# then it not possible
if maximum_split < k:
print("No")
return
print("Yes")
# Driver code
N = 12
K = 3
KPrimeDivisors(N, K)
C#
// C# implementation to Check if a
// number can be expressed as a
// product of exactly K prime divisors
using System;
class GFG {
// function to find K prime divisors
static void KPrimeDivisors(int N, int K)
{
int maximum_split = 0;
// count number of 2s that divide N
while (N % 2 == 0) {
maximum_split++;
N /= 2;
}
// N must be odd at this point.
// So we can skip one element
for (int i = 3; i * i <= N; i = i + 2) {
while (N % i == 0) {
// divide the value of N
N = N / i;
// increment count
maximum_split++;
}
}
// Condition to handle the case when n
// is a prime number greater than 2
if (N > 2)
maximum_split++;
// check if maximum_split is less than K
// then it not possible
if (maximum_split < K) {
Console.WriteLine("No");
return;
}
Console.WriteLine("Yes");
}
/* Driver code */
public static void Main(String[] args)
{
// initialise N and K
int N = 12;
int K = 3;
KPrimeDivisors(N, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript implementation to Check if a
// number can be expressed as a
// product of exactly K prime divisors
// function to find K prime divisors
function KPrimeDivisors(N , K)
{
var maximum_split = 0;
// count number of 2s that divide N
while (N % 2 == 0)
{
maximum_split++;
N /= 2;
}
// N must be odd at this point.
// So we can skip one element
for (i = 3; i * i <= N; i = i + 2)
{
while (N % i == 0)
{
// divide the value of N
N = N / i;
// increment count
maximum_split++;
}
}
// Condition to handle the case when n
// is a prime number greater than 2
if (N > 2)
maximum_split++;
// check if maximum_split is less than K
// then it not possible
if (maximum_split < K)
{
document.write("No");
return;
}
document.write("Yes");
}
/* Driver code */
// initialise N and K
var N = 12;
var K = 3;
KPrimeDivisors(N, K);
// This code is contributed by gauravrajput1.
</script>
Producción:
Yes
Complejidad del tiempo: O(sqrt(N))
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA