Comprobar si el número de factores pares e impares de un número son iguales

Posted on by Rudeus Greyrat

Dado un número N , la tarea es encontrar si N tiene el mismo número de factores pares e impares.
Ejemplos: 
 

Entrada: N = 10 
Salida: SI 
Explicación: 10 tiene dos factores impares (1 y 5) y dos factores pares (2 y 10)
Entrada: N = 24 
Salida: NO 
Explicación: 24 tiene dos factores impares (1 y 3) y seis factores pares (2, 4, 6, 8 12 y 24)
Entrada: N = 125 
Salida: NO 
 

Enfoque ingenuo: encuentre todos los divisores y verifique si el conteo de divisores impares es el mismo que el conteo de divisores pares.
A continuación se muestra la implementación del enfoque anterior. 
 

C++

// C++ solution for the above approach
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
 
// Function to check condition
void isEqualFactors(lli N)
{
    // Initialize even_count
    // and od_count
    lli ev_count = 0, od_count = 0;
 
    // loop runs till square root
    for (lli i = 1;
         i <= sqrt(N) + 1; i++) {
 
        if (N % i == 0) {
            if (i == N / i) {
                if (i % 2 == 0)
                    ev_count += 1;
                else
                    od_count += 1;
            }
 
            else {
                if (i % 2 == 0)
                    ev_count += 1;
                else
                    od_count += 1;
 
                if ((N / i) % 2 == 0)
                    ev_count += 1;
 
                else
                    od_count += 1;
            }
        }
    }
 
    if (ev_count == od_count)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
 
// Driver Code
int main()
{
    lli N = 10;
    isEqualFactors(N);
 
    return 0;
}

Java

// Java solution for the above approach
class GFG{
 
// Function to check condition
static void isEqualFactors(int N)
{
     
    // Initialize even_count
    // and od_count
    int ev_count = 0, od_count = 0;
 
    // Loop runs till square root
    for(int i = 1;
            i <= Math.sqrt(N) + 1; i++)
    {
       if (N % i == 0)
       {
           if (i == N / i)
           {
               if (i % 2 == 0)
                   ev_count += 1;
               else
                   od_count += 1;
           }
           else
           {
               if (i % 2 == 0)
                   ev_count += 1;
               else
                   od_count += 1;
                    
               if ((N / i) % 2 == 0)
                   ev_count += 1;
               else
                   od_count += 1;
           }
       }
    }
     
    if (ev_count == od_count)
        System.out.print("YES" + "\n");
    else
        System.out.print("NO" + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 10;
     
    isEqualFactors(N);
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 code for the naive approach
import math
 
# Function to check condition
def isEqualFactors(N):
 
# Initialize even_count
# and od_count
    ev_count = 0
    od_count = 0
 
# loop runs till square root
    for i in range(1, (int)(math.sqrt(N)) + 2) :
        if (N % i == 0):
            if(i == N // i):
                if(i % 2 == 0):
                    ev_count += 1
                else:
                    od_count += 1
             
            else:
                if(i % 2 == 0):
                    ev_count += 1
                else:
                    od_count += 1
                     
                if((N // i) % 2 == 0):
                    ev_count += 1;
                else:
                    od_count += 1;
     
    if (ev_count == od_count):
        print("YES")
    else:
        print("NO")
 
# Driver Code
N = 10
isEqualFactors(N)

C#

// C# solution for the above approach
using System;
 
class GFG{
 
// Function to check condition
static void isEqualFactors(int N)
{
     
    // Initialize even_count
    // and od_count
    int ev_count = 0, od_count = 0;
 
    // Loop runs till square root
    for(int i = 1;
            i <= Math.Sqrt(N) + 1; i++)
    {
        if (N % i == 0)
        {
            if (i == N / i)
            {
                if (i % 2 == 0)
                    ev_count += 1;
                else
                    od_count += 1;
            }
            else
            {
                if (i % 2 == 0)
                    ev_count += 1;
                else
                    od_count += 1;
                         
                if ((N / i) % 2 == 0)
                    ev_count += 1;
                else
                    od_count += 1;
            }
        }
    }
     
    if (ev_count == od_count)
        Console.Write("YES" + "\n");
    else
        Console.Write("NO" + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 10;
     
    isEqualFactors(N);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
// Javascript program for the above approach
 
// Function to check condition
function isEqualFactors(N)
{
     
    // Initialize even_count
    // and od_count
    let ev_count = 0, od_count = 0;
 
    // Loop runs till square root
    for(let i = 1;
            i <= Math.sqrt(N) + 1; i++)
    {
       if (N % i == 0)
       {
           if (i == N / i)
           {
               if (i % 2 == 0)
                   ev_count += 1;
               else
                   od_count += 1;
           }
           else
           {
               if (i % 2 == 0)
                   ev_count += 1;
               else
                   od_count += 1;
                    
               if ((N / i) % 2 == 0)
                   ev_count += 1;
               else
                   od_count += 1;
           }
       }
    }
     
    if (ev_count == od_count)
        document.write("YES" + "\n");
    else
        document.write("NO" + "\n");
}
 
    // Driver Code
     
    let N = 10;
     
    isEqualFactors(N);
 
</script>
Producción: 

YES

 

Complejidad de tiempo: O(sqrt(N)) 
Espacio auxiliar: O(1)
Solución eficiente: 
Se debe hacer la siguiente observación para optimizar el enfoque anterior: 
 

  • De acuerdo con el teorema de factorización única , cualquier número puede expresarse en términos del producto de la potencia de los números primos. Entonces, N se puede expresar como: 
     

 
 

N = P 1 A 1 * P 2 A 2 * P 3 A 3 * …….. * P k A K donde, cada P i es un número primo y cada A i es un número entero positivo.(1 <= i <= k) 
 

 

  • Usando la ley de los combinadores, cualquier divisor de N sería de la forma: 
     

N = P 1 B 1 * P 2 B 2 * P 3 B 3 * …….. * P K B K donde B i es un número entero y 0 <= B i <= A i for 1 <= i <= K . 
 

  • Un divisor sería impar si no contiene 2 en su descomposición en factores primos. Entonces, si P 1 = 2 entonces B 1 debe ser 0 . Se puede hacer de una sola manera.
  • Para divisores pares, B 1 puede ser reemplazado por 1 (o) 2 (o)….A 1 para obtener un divisor. Se puede hacer de las formas B 1 .
  • Ahora, para otros, cada B i se puede reemplazar con 0 (o) 1 (o) 2….(o) A i para 1 <= i <= K. Se puede hacer de (A i +1) formas.
  • Por principio fundamental: 
    • Número de divisores impares son: X = 1 * (A 2 +1) * (A 3 +1) * ….. * (A K +1).
    • Del mismo modo, Número de divisores pares son: Y = A 1 * (A 2 +1) * (A 3 +1) * …. * ( AK +1).
  • Para no. de divisores pares para ser igual a no. de divisores impares X, Y debe ser igual. Esto es posible solo cuando A 1 = 1 .

Entonces, se puede concluir que un número de divisores pares e impares de un número son iguales si tiene 1 (y solo 1) potencia de 2 en su descomposición en factores primos.
Siga los pasos a continuación para resolver el problema: 
 

  1. Para un número dado N, comprueba si es divisible por 2.
  2. Si el número es divisible por 2, comprueba si es divisible por 2 2 . Si es así, entonces el número no tendrá el mismo número de factores pares e impares. Si no, entonces el número tendrá el mismo número de factores pares e impares.
  3. Si el número no es divisible por 2, entonces el número nunca tendrá ningún factor par y, por lo tanto, no tendrá el mismo número de factores pares e impares.

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

C

// C code for the above approach
#include <stdio.h>
#define lli long long int
 
// Function to check condition
void isEqualFactors(lli N)
{
    if ((N % 2 == 0)
        && (N % 4 != 0))
        printf("YES\n");
    else
        printf("NO\n");
}
 
// Driver Code
int main()
{
    lli N = 10;
    isEqualFactors(N);
 
    N = 125;
    isEqualFactors(N);
 
    return 0;
}

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
 
// Function to check condition
void isEqualFactors(lli N)
{
    if ((N % 2 == 0)
        and (N % 4 != 0))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
 
// Driver Code
int main()
{
    lli N = 10;
    isEqualFactors(N);
 
    N = 125;
    isEqualFactors(N);
 
    return 0;
}

Java

// JAVA code for the above approach
public class GFG {
 
    // Function to check condition
    static void isEqualFactors(int N)
    {
        if ((N % 2 == 0)
            && (N % 4 != 0))
            System.out.println("YES");
 
        else
            System.out.println("NO");
    }
 
    // Driver code
    public static void main(String args[])
    {
        int N = 10;
        isEqualFactors(N);
 
        N = 125;
        isEqualFactors(N);
    }
}

Python

# Python code for the above approach
  
# Function to check condition
def isEqualFactors(N):
    if ( ( N % 2 == 0 ) and ( N % 4 != 0) ):
        print("YES")
    else:
        print("NO")
 
# Driver Code
N = 10
isEqualFactors(N)
 
N = 125;
isEqualFactors(N)

C#

// C# code for the above approach
using System;
 
class GFG {
 
    // Function to check condition
    static void isEqualFactors(int N)
    {
        if ((N % 2 == 0)
            && (N % 4 != 0))
            Console.WriteLine("YES");
 
        else
            Console.WriteLine("NO");
    }
 
    // Driver code
    public static void Main()
    {
        int N = 10;
        isEqualFactors(N);
 
        N = 125;
        isEqualFactors(N);
    }
}

Javascript

<script>
 
// Javascript code for the above approach
 
// Function to check condition
function isEqualFactors(N)
{
    if ((N % 2 == 0)
        && (N % 4 != 0))
        document.write("YES<br>");
    else
        document.write("NO<br>");
}
 
// Driver Code
var N = 10;
isEqualFactors(N);
N = 125;
isEqualFactors(N);
 
</script>
Producción: 

YES
NO

 

Tiempo Complejidad: O(1) 
Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por Chandan_Agrawal 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 *