Comprobar si existe un número con X divisores de los cuales Y son compuestos

Posted on by Rudeus Greyrat

Dados dos enteros X e Y que representan el número total de divisores y el número de divisores compuestos respectivamente, la tarea es comprobar si existe un número entero N que tenga exactamente X divisores e Y sean números compuestos.
 

Ejemplos:

 
Entrada: X = 6, Y = 3 
Salida: SÍ 
Explicación: 
N = 18 es ese número.
Los divisores de 18 son 1, 2, 3, 6, 9 y 18. 
Los divisores compuestos de 18 son 6, 9 y 18.
Entrada: X = 7, Y = 3 
Salida: NO 
Explicación: 
Vemos que no existe tal número que tiene 7 divisores positivos de los cuales 3 son divisores compuestos. 
 

Acercarse:  

  1. En primer lugar, calcula el número de divisores primos de un número, que es igual a:
     

                 Número de divisores primos = Número total de divisores – Número de divisores compuestos – 1 
 

  1. Entonces, el número de divisores primos, C = X – Y – 1 
     
  2. Dado que todo número tiene 1 como factor y 1 no es un número primo ni un número compuesto, tenemos que excluirlo de la cuenta en el número de divisores primos. 
     
  3. Si el número de divisores compuestos es menor que el número de divisores primos, entonces no es posible encontrar dicho número. 
     
  4. Entonces, si la descomposición en factores primos de X contiene al menos C enteros distintos, entonces es posible una solución. De lo contrario, no podemos encontrar un número N que satisfaga las condiciones dadas. 
     
  5. Encuentre el número máximo de valores en los que se puede descomponer X de modo que cada valor sea mayor que 1 . En otras palabras, podemos encontrar la descomposición en factores primos de X .
  6. Si esa descomposición en factores primos tiene un número de términos mayor o igual que C , entonces ese número es posible.

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program to check if a number
// exists having exactly X positive
// divisors out of which Y are
// composite divisors
#include <bits/stdc++.h>
using namespace std;
 
int factorize(int N)
{
    int count = 0;
    int cnt = 0;
 
    // Count the number of
    // times 2 divides N
    while ((N % 2) == 0) {
        N = N / 2;
        count++;
    }
 
    cnt = cnt + count;
 
    // check for all possible
    // numbers that can divide it
    for (int i = 3; i <= sqrt(N); i += 2) {
        count = 0;
        while (N % i == 0) {
            count++;
            N = N / i;
        }
        cnt = cnt + count;
    }
 
    // if N at the end
    // is a prime number.
    if (N > 2)
        cnt = cnt + 1;
    return cnt;
}
 
// Function to check if any
// such number exists
void ifNumberExists(int X, int Y)
{
    int C, dsum;
 
    C = X - Y - 1;
    dsum = factorize(X);
    if (dsum >= C)
        cout << "YES \n";
    else
        cout << "NO \n";
}
 
// Driver Code
int main()
{
 
    int X, Y;
    X = 6;
    Y = 4;
 
    ifNumberExists(X, Y);
    return 0;
}

Java

// Java program to check if a number
// exists having exactly X positive
// divisors out of which Y are
// composite divisors
import java.lang.Math;
class GFG{
     
public static int factorize(int N)
{
    int count = 0;
    int cnt = 0;
     
    // Count the number of
    // times 2 divides N
    while ((N % 2) == 0)
    {
        N = N / 2;
        count++;
    }
     
    cnt = cnt + count;
     
    // Check for all possible
    // numbers that can divide it
    for(int i = 3; i <= Math.sqrt(N); i += 2)
    {
       count = 0;
       while (N % i == 0)
       {
           count++;
           N = N / i;
       }
       cnt = cnt + count;
    }
     
    // If N at the end
    // is a prime number.
    if (N > 2)
        cnt = cnt + 1;
    return cnt;
}
     
// Function to check if any
// such number exists
public static void ifNumberExists(int X, int Y)
{
    int C, dsum;
    C = X - Y - 1;
    dsum = factorize(X);
         
    if (dsum >= C)
        System.out.println("YES");
    else
        System.out.println("NO");
}
 
// Driver code   
public static void main(String[] args)
{
    int X, Y;
    X = 6;
    Y = 4;
     
    ifNumberExists(X, Y);
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 program to check if a number exists
# having exactly X positive divisors out of
#  which Y are composite divisors
import math
 
def factorize(N):
 
    count = 0
    cnt = 0
 
    # Count the number of
    # times 2 divides N
    while ((N % 2) == 0):
        N = N // 2
        count+=1
 
    cnt = cnt + count
 
    # Check for all possible
    # numbers that can divide it
    sq = int(math.sqrt(N))
    for i in range(3, sq, 2):
        count = 0
         
        while (N % i == 0):
            count += 1
            N = N // i
         
        cnt = cnt + count
 
    # If N at the end
    # is a prime number.
    if (N > 2):
        cnt = cnt + 1
    return cnt
 
# Function to check if any
# such number exists
def ifNumberExists(X, Y):
 
    C = X - Y - 1
    dsum = factorize(X)
     
    if (dsum >= C):
        print ("YES")
    else:
        print("NO")
 
# Driver Code
if __name__ == "__main__":
     
    X = 6
    Y = 4
 
    ifNumberExists(X, Y)
 
# This code is contributed by chitranayal

C#

// C# program to check if a number
// exists having exactly X positive
// divisors out of which Y are
// composite divisors
using System;
class GFG{
 
public static int factorize(int N)
{
    int count = 0;
    int cnt = 0;
     
    // Count the number of
    // times 2 divides N
    while ((N % 2) == 0)
    {
        N = N / 2;
        count++;
    }
     
    cnt = cnt + count;
     
    // Check for all possible
    // numbers that can divide it
    for(int i = 3; i <= Math.Sqrt(N); i += 2)
    {
        count = 0;
        while (N % i == 0)
        {
            count++;
            N = N / i;
        }
        cnt = cnt + count;
    }
     
    // If N at the end
    // is a prime number.
    if (N > 2)
        cnt = cnt + 1;
    return cnt;
}
     
// Function to check if any
// such number exists
public static void ifNumberExists(int X, int Y)
{
    int C, dsum;
    C = X - Y - 1;
    dsum = factorize(X);
         
    if (dsum >= C)
        Console.WriteLine("YES");
    else
        Console.WriteLine("NO");
}
 
// Driver code
public static void Main(string[] args)
{
    int X, Y;
    X = 6;
    Y = 4;
     
    ifNumberExists(X, Y);
}
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
// javascript program to check if a number
// exists having exactly X positive
// divisors out of which Y are
// composite divisors
 
    function factorize(N) {
        var count = 0;
        var cnt = 0;
 
        // Count the number of
        // times 2 divides N
        while ((N % 2) == 0) {
            N = N / 2;
            count++;
        }
 
        cnt = cnt + count;
 
        // Check for all possible
        // numbers that can divide it
        for (i = 3; i <= Math.sqrt(N); i += 2) {
            count = 0;
            while (N % i == 0) {
                count++;
                N = N / i;
            }
            cnt = cnt + count;
        }
 
        // If N at the end
        // is a prime number.
        if (N > 2)
            cnt = cnt + 1;
        return cnt;
    }
 
    // Function to check if any
    // such number exists
    function ifNumberExists(X , Y) {
        var C, dsum;
        C = X - Y - 1;
        dsum = factorize(X);
 
        if (dsum >= C)
            document.write("YES");
        else
            document.write("NO");
    }
 
    // Driver code
     
        var X, Y;
        X = 6;
        Y = 4;
 
        ifNumberExists(X, Y);
 
// This code is contributed by todaysgaurav
</script>
Producción: 

YES

 

Complejidad Temporal: O (N 1/2 )  
Espacio Auxiliar: O (1)
 

Publicación traducida automáticamente

Artículo escrito por diya_nc y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *