Recuento de enteros que dividen todos los elementos de la array dada

Dada una array arr[] de N elementos. La tarea es encontrar el conteo de enteros positivos que dividen todos los elementos del arreglo.
Ejemplos: 
 

Entrada: arr[] = {2, 8, 10, 6} 
Salida:
1 y 2 son los únicos números enteros que dividen 
todos los elementos de la array dada.
Entrada: arr[] = {6, 12, 18, 12, 6} 
Salida:
 

Enfoque: Sabemos que el entero máximo que dividirá todos los elementos del arreglo será el mcd del arreglo y todos los demás enteros que dividirán todos los elementos del arreglo tendrán que ser los factores de este mcd. Por lo tanto, el conteo de enteros válidos será igual al conteo de factores del gcd de todos los elementos del arreglo.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// the required integers
int getCount(int a[], int n)
{
 
    // To store the gcd of the array elements
    int gcd = 0;
    for (int i = 0; i < n; i++)
        gcd = __gcd(gcd, a[i]);
 
    // To store the count of factors
    // of the found gcd
    int cnt = 0;
 
    for (int i = 1; i * i <= gcd; i++) {
        if (gcd % i == 0) {
 
            // If g is a perfect square
            if (i * i == gcd)
                cnt++;
 
            // Factors appear in pairs
            else
                cnt += 2;
        }
    }
 
    return cnt;
}
 
// Driver code
int main()
{
    int a[] = { 4, 16, 1024, 48 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << getCount(a, n);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
    // Recursive function to return gcd
    static int calgcd(int a, int b)
    {
        if (b == 0)
            return a;
        return calgcd(b, a % b);
    }
     
    // Function to return the count of
    // the required integers
    static int getCount(int [] a, int n)
    {
     
        // To store the gcd of the array elements
        int gcd = 0;
        for (int i = 0; i < n; i++)
            gcd = calgcd(gcd, a[i]);
     
        // To store the count of factors
        // of the found gcd
        int cnt = 0;
     
        for (int i = 1; i * i <= gcd; i++)
        {
            if (gcd % i == 0)
            {
     
                // If g is a perfect square
                if (i * i == gcd)
                    cnt++;
     
                // Factors appear in pairs
                else
                    cnt += 2;
            }
        }
        return cnt;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int [] a = { 4, 16, 1024, 48 };
        int n = a.length;
     
        System.out.println(getCount(a, n));
    }
}
 
// This code is contributed by ihritik

Python3

# Python3 implementation of the approach
 
# Function to return the count of
# the required integers
from math import gcd as __gcd
def getCount(a, n):
 
    # To store the gcd of the array elements
    gcd = 0
    for i in range(n):
        gcd = __gcd(gcd, a[i])
 
    # To store the count of factors
    # of the found gcd
    cnt = 0
 
    for i in range(1, gcd + 1):
        if i * i > gcd:
            break
        if (gcd % i == 0):
 
            # If g is a perfect square
            if (i * i == gcd):
                cnt += 1
 
            # Factors appear in pairs
            else:
                cnt += 2
 
    return cnt
 
# Driver code
a = [4, 16, 1024, 48]
n = len(a)
 
print(getCount(a, n))
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Recursive function to return gcd
    static int calgcd(int a, int b)
    {
        if (b == 0)
            return a;
        return calgcd(b, a % b);
    }
     
    // Function to return the count of
    // the required integers
    static int getCount(int [] a, int n)
    {
     
        // To store the gcd of the array elements
        int gcd = 0;
        for (int i = 0; i < n; i++)
            gcd = calgcd(gcd, a[i]);
     
        // To store the count of factors
        // of the found gcd
        int cnt = 0;
     
        for (int i = 1; i * i <= gcd; i++)
        {
            if (gcd % i == 0)
            {
     
                // If g is a perfect square
                if (i * i == gcd)
                    cnt++;
     
                // Factors appear in pairs
                else
                    cnt += 2;
            }
        }
        return cnt;
    }
     
    // Driver code
    public static void Main ()
    {
        int [] a = { 4, 16, 1024, 48 };
        int n = a.Length;
     
        Console.WriteLine(getCount(a, n));
    }
}
 
// This code is contributed by ihritik

Javascript

<script>
 
// Javascript implementation of the approach
 
function calgcd(a, b)
{
    if (b == 0)
        return a;
    return calgcd(b, a % b);
}
     
// Function to return the count of
// the required integers
function getCount(a, n)
{
 
    // To store the gcd of the array elements
    let gcd = 0;
    for (let i = 0; i < n; i++)
        gcd = calgcd(gcd, a[i]);
 
    // To store the count of factors
    // of the found gcd
    let cnt = 0;
 
    for (let i = 1; i * i <= gcd; i++) {
        if (gcd % i == 0) {
 
            // If g is a perfect square
            if (i * i == gcd)
                cnt++;
 
            // Factors appear in pairs
            else
                cnt += 2;
        }
    }
 
    return cnt;
}
 
// Driver code
    let a = [ 4, 16, 1024, 48 ];
    let n = a.length;
 
    document.write(getCount(a, n));
 
</script>
Producción: 

3

 

Publicación traducida automáticamente

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