Conteo de pares en un Array dado cuyo GCD no es primo

Dada una array arr[] que consiste en N enteros positivos, la tarea es encontrar el número de pares tal que el Máximo Común Divisor (MCD) de los pares no sea un número primo . El par (i, j) y (j, i) se consideran iguales.

Ejemplos:

Entrada: arr[] ={ 2, 3, 9}
Salida: 10
Explicación:
Los siguientes son los posibles pares cuyo MCD no es primo:

(0, 1): El MCD de arr[0](= 2) y arr[1](= 3) es 1.

(0, 2): El MCD de arr[0](= 2) y arr[2](= 9) es 1.

Por lo tanto, la cuenta total de pares es 2.

Entrada: arr[] = {3, 5, 2, 10}
Salida: 4

Enfoque: El problema dado se puede resolver encontrando todos los números primos hasta 10 ⁵ y almacenándolos en un Conjunto y luego para cada par (i, j) si su MCD no está en el conjunto, luego cuente este par. Siga los pasos a continuación para resolver el problema:

Defina una función primeSieve() y encuentre números primos hasta 10 ⁵ usando la criba de Eratóstenes y guárdela en un conjunto desordenado , digamos S.
Inicialice la variable, digamos contar como 0 que almacena el recuento total de pares.
Genere todos los pares posibles de la array dada y, si su GCD no se encuentra en el conjunto, incremente el valor de count en 1 .
Después de realizar los pasos anteriores, imprima el valor de conteo como respuesta.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the prime numbers
void primeSieve(bool* p)
{
    for (int i = 2; i * i <= 1000000; i++) {
 
        // If p[i] is not changed,
        // then it is a prime
        if (p[i] == true) {
 
            // Update all multiples of i
            // as non prime
            for (int j = i * 2;
                 j <= 1000000; j += i) {
                p[j] = false;
            }
        }
    }
}
 
// Function to find GCD of two integers
// a and b
int gcd(int a, int b)
{
    // Base Case
    if (b == 0)
        return a;
 
    // Find GCD Recursively
    return gcd(b, a % b);
}
 
// Function to count the number of
// pairs whose GCD is non prime
int countPairs(int arr[], int n,
               unordered_set<int> s)
{
    // Stores the count of valid pairs
    int count = 0;
 
    // Traverse over the array arr[]
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
 
            // Calculate the GCD
            int x = gcd(arr[i], arr[j]);
 
            // Update the count
            if (s.find(x) == s.end())
                count++;
        }
    }
 
    // Return count
    return count;
}
 
// Utility Function to find all the prime
// numbers and find all the pairs
void countPairsUtil(int arr[], int n)
{
    // Stores all the prime numbers
    unordered_set<int> s;
    bool p[1000005];
    memset(p, true, sizeof(p));
 
    // Find all the prime numbers
    primeSieve(p);
 
    s.insert(2);
 
    // Insert prime numbers in the
    // unordered set
    for (int i = 3; i <= 1000000; i += 2)
        if (p[i])
            s.insert(i);
 
    // Find the count of valid pairs
    cout << countPairs(arr, n, s);
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 3, 9 };
    int N = sizeof(arr) / sizeof(arr[0]);
    countPairsUtil(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the prime numbers
static void primeSieve(boolean[] p)
{
    for (int i = 2; i * i <= 1000000; i++) {
 
        // If p[i] is not changed,
        // then it is a prime
        if (p[i] == true) {
 
            // Update all multiples of i
            // as non prime
            for (int j = i * 2;
                 j <= 1000000; j += i) {
                p[j] = false;
            }
        }
    }
}
 
// Function to find GCD of two integers
// a and b
static int gcd(int a, int b)
{
    // Base Case
    if (b == 0)
        return a;
 
    // Find GCD Recursively
    return gcd(b, a % b);
}
 
// Function to count the number of
// pairs whose GCD is non prime
static int countPairs(int arr[], int n,
               HashSet<Integer> s)
{
    // Stores the count of valid pairs
    int count = 0;
 
    // Traverse over the array arr[]
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
 
            // Calculate the GCD
            int x = gcd(arr[i], arr[j]);
 
            // Update the count
            if (!s.contains(x))
                count++;
        }
    }
 
    // Return count
    return count;
}
 
// Utility Function to find all the prime
// numbers and find all the pairs
static void countPairsUtil(int arr[], int n)
{
    // Stores all the prime numbers
    HashSet<Integer> s = new HashSet<Integer>();
    boolean []p = new boolean[1000005];
    for(int i=0;i<p.length;i++)
        p[i] = true;
 
    // Find all the prime numbers
    primeSieve(p);
 
    s.add(2);
 
    // Insert prime numbers in the
    // unordered set
    for (int i = 3; i <= 1000000; i += 2)
        if (p[i])
            s.add(i);
 
    // Find the count of valid pairs
    System.out.print(countPairs(arr, n, s));
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 2, 3, 9 };
    int N = arr.length;
    countPairsUtil(arr, N);
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python 3 program for the above approach
 
from math import sqrt,gcd
 
# Function to find the prime numbers
def primeSieve(p):
    for i in range(2,int(sqrt(1000000)),1):
       
        # If p[i] is not changed,
        # then it is a prime
        if (p[i] == True):
 
            # Update all multiples of i
            # as non prime
            for j in range(i * 2,1000001,i):
                p[j] = False
 
# Function to count the number of
# pairs whose GCD is non prime
def countPairs(arr, n, s):
   
    # Stores the count of valid pairs
    count = 0
 
    # Traverse over the array arr[]
    for i in range(n - 1):
        for j in range(i + 1,n,1):
           
            # Calculate the GCD
            x = gcd(arr[i], arr[j])
 
            # Update the count
            if (x not in s):
                count += 1
 
    # Return count
    return count
 
# Utility Function to find all the prime
# numbers and find all the pairs
def countPairsUtil(arr, n):
   
    # Stores all the prime numbers
    s = set()
    p = [True for  i in range(1000005)]
 
    # Find all the prime numbers
    primeSieve(p)
 
    s.add(2)
 
    # Insert prime numbers in the
    # unordered set
    for i in range(3,1000001,2):
        if (p[i]):
            s.add(i)
 
    # Find the count of valid pairs
    print(countPairs(arr, n, s))
 
# Driver Code
if __name__ == '__main__':
    arr = [2, 3, 9]
    N = len(arr)
    countPairsUtil(arr, N)
     
    # This code is contributed by SURENDRA_GANGWAR.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
// Function to find the prime numbers
static void primeSieve(bool[] p)
{
    for (int i = 2; i * i <= 1000000; i++) {
 
        // If p[i] is not changed,
        // then it is a prime
        if (p[i] == true) {
 
            // Update all multiples of i
            // as non prime
            for (int j = i * 2;
                 j <= 1000000; j += i) {
                p[j] = false;
            }
        }
    }
}
 
// Function to find GCD of two integers
// a and b
static int gcd(int a, int b)
{
    // Base Case
    if (b == 0)
        return a;
 
    // Find GCD Recursively
    return gcd(b, a % b);
}
 
// Function to count the number of
// pairs whose GCD is non prime
static int countPairs(int []arr, int n,
               HashSet<int> s)
{
    // Stores the count of valid pairs
    int count = 0;
 
    // Traverse over the array []arr
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
 
            // Calculate the GCD
            int x = gcd(arr[i], arr[j]);
 
            // Update the count
            if (!s.Contains(x))
                count++;
        }
    }
 
    // Return count
    return count;
}
 
// Utility Function to find all the prime
// numbers and find all the pairs
static void countPairsUtil(int []arr, int n)
{
   
    // Stores all the prime numbers
    HashSet<int> s = new HashSet<int>();
    bool []p = new bool[1000005];
    for(int i = 0; i < p.Length; i++)
        p[i] = true;
 
    // Find all the prime numbers
    primeSieve(p);
 
    s.Add(2);
 
    // Insert prime numbers in the
    // unordered set
    for (int i = 3; i <= 1000000; i += 2)
        if (p[i])
            s.Add(i);
 
    // Find the count of valid pairs
    Console.Write(countPairs(arr, n, s));
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 2, 3, 9 };
    int N = arr.Length;
    countPairsUtil(arr, N);
 
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript program for the above approach
 
    // Function to find the prime numbers
    function primeSieve( p) {
        for (var i = 2; i * i <= 1000000; i++) {
 
            // If p[i] is not changed,
            // then it is a prime
            if (p[i] == true) {
 
                // Update all multiples of i
                // as non prime
                for (j = i * 2; j <= 1000000; j += i) {
                    p[j] = false;
                }
            }
        }
    }
 
    // Function to find GCD of two integers
    // a and b
    function gcd(a, b)
    {
        // Base Case
        if (b == 0)
            return a;
 
        // Find GCD Recursively
        return gcd(b, a % b);
    }
 
    // Function to count the number of
    // pairs whose GCD is non prime
    function countPairs(arr , n, s) {
        // Stores the count of valid pairs
        var count = 0;
 
        // Traverse over the array arr
        for (var i = 0; i < n - 1; i++) {
            for (var j = i + 1; j < n; j++) {
 
                // Calculate the GCD
                var x = gcd(arr[i], arr[j]);
 
                // Update the count
                if (!s.has(x))
                    count++;
            }
        }
 
        // Return count
        return count;
    }
 
    // Utility Function to find all the prime
    // numbers and find all the pairs
    function countPairsUtil(arr, n)
    {
     
        // Stores all the prime numbers
        var s = new Set();
        var p = Array(1000005).fill(false);
        for (var i = 0; i < p.length; i++)
            p[i] = true;
 
        // Find all the prime numbers
        primeSieve(p);
 
        s.add(2);
 
        // Insert prime numbers in the
        // unordered set
        for (i = 3; i <= 1000000; i += 2)
            if (p[i])
                s.add(i);
 
        // Find the count of valid pairs
        document.write(countPairs(arr, n, s));
    }
 
    // Driver Code
        var arr = [ 2, 3, 9 ];
        var N = arr.length;
        countPairsUtil(arr, N);
 
// This code is contributed by gauravrajput1
</script>

Producción:

Complejidad de Tiempo: O((N ² )*log N)
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta