Dados dos números N y K , la tarea es encontrar si existe un entero X tal que tenga exactamente N factores y K de ellos sean primos.
Ejemplos:
Entrada: N = 4, K = 2
Salida: Sí
Explicación:
Un número posible para X es 6.
El número 6 tiene un total de 4 factores: 1, 2, 3 y 6.
También tiene exactamente 2 factores primos: 2 y 3
Entrada: N = 3, K = 1
Salida: Sí
Explicación:
Un número posible para X es 49.
El número 49 tiene un total de 3 factores: 1, 7 y 49.
También tiene exactamente 1 factor primo: 7.
Enfoque: La idea es utilizar la siguiente identidad.
- Para cualquier número X, si el número tiene N factores de los cuales K son primos:
X = k1a + k2b + k3c + ... + knn
- El número total de factores N es igual a:
N = (a + 1) * (b + 1) * (c + 1) .. (n + 1)
- Por lo tanto, la idea es verificar si N se puede representar como un producto de K enteros mayores que 1. Esto se puede hacer encontrando los divisores del número N.
- Si la cuenta de esto es menor que K, entonces la respuesta no es posible. De lo contrario, es posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if it
// is possible to make a number
// having total N factors and
// K prime factors
#include <bits/stdc++.h>
using namespace std;
// Function to compute the
// number of factors of
// the given number
bool factors(int n, int k)
{
// Vector to store
// the prime factors
vector<int> v;
// While there are no
// two multiples in
// the number, divide
// it by 2
while (n % 2 == 0) {
v.push_back(2);
n /= 2;
}
// If the size is already
// greater than K,
// then return true
if (v.size() >= k)
return true;
// Computing the remaining
// divisors of the number
for (int i = 3; i * i <= n;
i += 2) {
// If n is divisible by i,
// then it is a divisor
while (n % i == 0) {
n = n / i;
v.push_back(i);
}
// If the size is already
// greater than K, then
// return true
if (v.size() >= k)
return true;
}
if (n > 2)
v.push_back(n);
// If the size is already
// greater than K,
// then return true
if (v.size() >= k)
return true;
// If none of the above
// conditions satisfies,
// then return false
return false;
}
// Function to check if it is
// possible to make a number
// having total N factors and
// K prime factors
void operation(int n, int k)
{
bool answered = false;
// If total divisors are
// less than the number
// of prime divisors,
// then print No
if (n < k) {
answered = true;
cout << "No"
<< "\n";
}
// Find the number of
// factors of n
bool ok = factors(n, k);
if (!ok && !answered) {
answered = true;
cout << "No"
<< "\n";
}
if (ok && !answered)
cout << "Yes"
<< "\n";
}
// Driver Code
int main()
{
int n = 4;
int k = 2;
operation(n, k);
return 0;
}
Java
// Java program to check if it
// is possible to make a number
// having total N factors and
// K prime factors
import java.io.*;
import java.util.*;
class GFG{
// Function to compute the
// number of factors of
// the given number
static boolean factors(int n, int k)
{
// Vector to store
// the prime factors
ArrayList<Integer> v = new ArrayList<Integer>();
// While there are no
// two multiples in
// the number, divide
// it by 2
while (n % 2 == 0)
{
v.add(2);
n /= 2;
}
// If the size is already
// greater than K,
// then return true
if (v.size() >= k)
return true;
// Computing the remaining
// divisors of the number
for(int i = 3; i * i <= n; i += 2)
{
// If n is divisible by i,
// then it is a divisor
while (n % i == 0)
{
n = n / i;
v.add(i);
}
// If the size is already
// greater than K, then
// return true
if (v.size() >= k)
return true;
}
if (n > 2)
v.add(n);
// If the size is already
// greater than K,
// then return true
if (v.size() >= k)
return true;
// If none of the above
// conditions satisfies,
// then return false
return false;
}
// Function to check if it is
// possible to make a number
// having total N factors and
// K prime factors
static void operation(int n, int k)
{
boolean answered = false;
// If total divisors are
// less than the number
// of prime divisors,
// then print No
if (n < k)
{
answered = true;
System.out.println("No");
}
// Find the number of
// factors of n
boolean ok = factors(n, k);
if (!ok && !answered)
{
answered = true;
System.out.println("No");
}
if (ok && !answered)
System.out.println("Yes");
}
// Driver code
public static void main(String[] args)
{
int n = 4;
int k = 2;
//Function call
operation(n, k);
}
}
// This code is contributed by coder001
Python3
# Python3 program to check if it
# is possible to make a number
# having total N factors and
# K prime factors
# Function to compute the
# number of factors of
# the given number
def factors(n, k):
# Vector to store
# the prime factors
v = [];
# While there are no
# two multiples in
# the number, divide
# it by 2
while (n % 2 == 0):
v.append(2);
n //= 2;
# If the size is already
# greater than K,
# then return true
if (len(v) >= k):
return True;
# Computing the remaining
# divisors of the number
for i in range(3, int(n ** (1 / 2)), 2):
# If n is divisible by i,
# then it is a divisor
while (n % i == 0):
n = n // i;
v.append(i);
# If the size is already
# greater than K, then
# return true
if (len(v) >= k):
return True;
if (n > 2):
v.append(n);
# If the size is already
# greater than K,
# then return true
if (len(v) >= k):
return True;
# If none of the above
# conditions satisfies,
# then return false
return False;
# Function to check if it is
# possible to make a number
# having total N factors and
# K prime factors
def operation(n, k):
answered = False;
# If total divisors are
# less than the number
# of prime divisors,
# then print No
if (n < k):
answered = True;
print("No");
# Find the number of
# factors of n
ok = factors(n, k);
if (not ok and not answered):
answered = True;
print("No");
if (ok and not answered):
print("Yes");
# Driver Code
if __name__ == "__main__":
n = 4;
k = 2;
operation(n, k);
# This code is contributed by AnkitRai01
C#
// C# program to check if it
// is possible to make a number
// having total N factors and
// K prime factors
using System;
using System.Collections.Generic;
class GFG{
// Function to compute the
// number of factors of
// the given number
static bool factors(int n, int k)
{
// Vector to store
// the prime factors
List<int> v = new List<int>();
// While there are no
// two multiples in
// the number, divide
// it by 2
while (n % 2 == 0)
{
v.Add(2);
n /= 2;
}
// If the size is already
// greater than K,
// then return true
if (v.Count >= k)
return true;
// Computing the remaining
// divisors of the number
for(int i = 3; i * i <= n; i += 2)
{
// If n is divisible by i,
// then it is a divisor
while (n % i == 0)
{
n = n / i;
v.Add(i);
}
// If the size is already
// greater than K, then
// return true
if (v.Count >= k)
return true;
}
if (n > 2)
v.Add(n);
// If the size is already
// greater than K,
// then return true
if (v.Count >= k)
return true;
// If none of the above
// conditions satisfies,
// then return false
return false;
}
// Function to check if it is
// possible to make a number
// having total N factors and
// K prime factors
static void operation(int n, int k)
{
bool answered = false;
// If total divisors are
// less than the number
// of prime divisors,
// then print No
if (n < k)
{
answered = true;
Console.WriteLine("No");
}
// Find the number of
// factors of n
bool ok = factors(n, k);
if (!ok && !answered)
{
answered = true;
Console.WriteLine("No");
}
if (ok && !answered)
Console.WriteLine("Yes");
}
// Driver code
public static void Main()
{
int n = 4;
int k = 2;
// Function call
operation(n, k);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to check if it
// is possible to make a number
// having total N factors and
// K prime factors
// Function to compute the
// number of factors of
// the given number
function factors(n, k)
{
// Vector to store
// the prime factors
let v = [];
// While there are no
// two multiples in
// the number, divide
// it by 2
while (n % 2 == 0) {
v.push(2);
n = parseInt(n/2);
}
// If the size is already
// greater than K,
// then return true
if (v.length >= k)
return true;
// Computing the remaining
// divisors of the number
for (let i = 3; i * i <= n;
i += 2) {
// If n is divisible by i,
// then it is a divisor
while (n % i == 0) {
n = parseInt(n / i);
v.push(i);
}
// If the size is already
// greater than K, then
// return true
if (v.length >= k)
return true;
}
if (n > 2)
v.push(n);
// If the size is already
// greater than K,
// then return true
if (v.length >= k)
return true;
// If none of the above
// conditions satisfies,
// then return false
return false;
}
// Function to check if it is
// possible to make a number
// having total N factors and
// K prime factors
function operation(n, k)
{
let answered = false;
// If total divisors are
// less than the number
// of prime divisors,
// then print No
if (n < k) {
answered = true;
document.write("No<br>");
}
// Find the number of
// factors of n
let ok = factors(n, k);
if (!ok && !answered) {
answered = true;
document.write("No<br>");
}
if (ok && !answered)
document.write("Yes<br>");
}
// Driver Code
let n = 4;
let k = 2;
operation(n, k);
</script>
Producción:
Yes
Complejidad de tiempo: O (n 1/2 )
Espacio Auxiliar: O(n 1/2 )
Publicación traducida automáticamente
Artículo escrito por Adityasharma15 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA