Dada una array , arr[] de tamaño N , la tarea es contar todos los pares de la array dada cuyo producto es un número compuesto .
Ejemplos:
Entrada: arr[] = {1, 4, 7}
Salida: 2
Explicación:
Los pares cuyo producto es un número compuesto son: (4, 7), (1, 4).
Por lo tanto, la salida requerida es 2.Entrada: arr[] = {1, 2, 8, 10}
Salida: 5
Enfoque ingenuo: la idea es atravesar la array y generar todos los pares posibles de la array dada . Para cada par, comprueba si el producto de sus elementos es un número compuesto o no. Si es cierto, entonces incremente el conteo en 1. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res para almacenar el recuento de pares cuyo producto es un número compuesto .
- Recorre la array y genera todos los pares posibles de la array dada.
- Para cada par, verifique si su producto es compuesto o no. Si se determina que es cierto, entonces incremente el valor de res en 1 .
- Finalmente, imprima el valor de res .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a
// number is prime or not
bool isComposite(int N)
{
// Check if N is multiple
// of i or not.
for (int i = 2; i * i <= N;
i++) {
// If N is multiple of i.
if (N % i == 0) {
return true;
}
}
return false;
}
// Function to get the count
// of pairs whose product
// is a composite number.
int compositePair(int arr[], int N)
{
// Stores the count of pairs
// whose product is
// a composite number
int res = 0;
// Generate all possible pairs
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N;
j++) {
// Stores the product of
// element of current pair
int prod = arr[i] * arr[j];
// If prod is a
// composite number
if (isComposite(prod)) {
res++;
}
}
}
return res;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 2, 2, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << compositePair(arr, N);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.io.*;
class GFG{
// Function to check if a
// number is prime or not
static boolean isComposite(int N)
{
// Check if N is multiple
// of i or not.
for (int i = 2; i * i <= N; i++)
{
// If N is multiple of i.
if (N % i == 0)
{
return true;
}
}
return false;
}
// Function to get the count
// of pairs whose product
// is a composite number.
static int compositePair(int arr[],
int N)
{
// Stores the count of pairs
// whose product is
// a composite number
int res = 0;
// Generate all possible pairs
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
// Stores the product of
// element of current pair
int prod = arr[i] * arr[j];
// If prod is a
// composite number
if (isComposite(prod))
{
res++;
}
}
}
return res;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {1, 1, 2, 2, 8};
int N = arr.length;
System.out.println(compositePair(arr, N));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program to implement # the above approach # Function to check if a # number is prime or not def isComposite(N): # Check if N is multiple # of i or not. for i in range(2, N + 1): if i * i > N: break # If N is multiple of i. if (N % i == 0): return True return False # Function to get the count # of pairs whose product # is a composite number. def compositePair(arr, N): # Stores the count of pairs # whose product is # a composite number res = 0 # Generate all possible pairs for i in range(N): for j in range(i + 1, N): # Stores the product of # element of current pair prod = arr[i] * arr[j] # If prod is a # composite number if (isComposite(prod)): res += 1 return res # Driver Code if __name__ == '__main__': arr = [ 1, 1, 2, 2, 8 ] N = len(arr) print(compositePair(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# Program to implement
// the above approach
using System;
class GFG{
// Function to check if a
// number is prime or not
static bool isComposite(int N)
{
// Check if N is multiple
// of i or not.
for (int i = 2; i * i <= N; i++)
{
// If N is multiple of i.
if (N % i == 0)
{
return true;
}
}
return false;
}
// Function to get the count
// of pairs whose product
// is a composite number.
static int compositePair(int []arr,
int N)
{
// Stores the count of pairs
// whose product is
// a composite number
int res = 0;
// Generate all possible pairs
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
// Stores the product of
// element of current pair
int prod = arr[i] * arr[j];
// If prod is a
// composite number
if (isComposite(prod))
{
res++;
}
}
}
return res;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {1, 1, 2, 2, 8};
int N = arr.Length;
Console.WriteLine(compositePair(arr, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to check if a
// number is prime or not
function isComposite(N)
{
var i;
// Check if N is multiple
// of i or not.
for(i = 2; i * i <= N; i++) {
// If N is multiple of i.
if (N % i == 0) {
return true;
}
}
return false;
}
// Function to get the count
// of pairs whose product
// is a composite number.
function compositePair(arr, N)
{
// Stores the count of pairs
// whose product is
// a composite number
var res = 0;
var i,j;
// Generate all possible pairs
for(i = 0; i < N; i++) {
for (j = i + 1; j < N;
j++) {
// Stores the product of
// element of current pair
var prod = arr[i] * arr[j];
// If prod is a
// composite number
if (isComposite(prod)) {
res++;
}
}
}
return res;
}
// Driver Code
var arr = [1, 1, 2, 2, 8];
var N = arr.length;
document.write(compositePair(arr, N));
</script>
Producción
5
Complejidad temporal: O(N 2 √X), donde X es el producto máximo posible de un par en el arreglo dado.
Espacio Auxiliar: O(1)
Enfoque eficiente: PARA optimizar el enfoque anterior, la idea es utilizar el hecho de que todos los números primos y los 1 no son números compuestos. Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables cntPrime y cntOne para almacenar el conteo de 1 y números primos en la array dada, respectivamente.
- Inicialice una variable, digamos res para almacenar el conteo de pares cuyo producto es un número compuesto.
- El total de pares cuyo producto no es un número compuesto es:
cntNonComp = cntPrime × cntOne + cntOne × (cntOne – 1) / 2.
- Por lo tanto, la cuenta total de pares cuyo producto es un número compuesto es:
res = N × (N – 1) / 2 – cntNonComp.
- Finalmente, imprima el valor de res .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define X 1000000
// Function to get all
// the prime numbers in
// the range[1, X]
vector<bool> getPrimeNum()
{
// Stores the boolean value
// to check if a number is
// prime or not
vector<bool> isPrime(X, true);
isPrime[0] = false;
isPrime[1] = false;
// Mark all non prime
// numbers as false
for (int i = 2; i * i <= X;
i++) {
// If i is prime number
if (isPrime[i] == true) {
for (int j = i * i;
j < X; j += i) {
// Mark j as
// a composite number
isPrime[j] = false;
}
}
}
return isPrime;
}
// Function to get the count of pairs
// whose product is a composite number
int cntPairs(int arr[], int N)
{
// Stores the boolean value
// to check if a number is
// prime or not
vector<bool> isPrime
= getPrimeNum();
// Stores the count of 1s
int cntOne = 0;
// Stores the count
// of prime numbers
int cntPrime = 0;
// Traverse the given array.
for (int i = 0; i < N; i++) {
if (arr[i] == 1) {
cntOne += 1;
}
else if (isPrime[i]) {
cntPrime += 1;
}
}
// Stores count of pairs whose
// product is not a composite number
int cntNonComp = 0;
cntNonComp = cntPrime * cntOne
+ cntOne * (cntOne - 1) / 2;
// Stores the count of pairs
// whose product is composite number
int res = 0;
res = N * (N - 1) / 2 - cntNonComp;
return res;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 2, 2, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << cntPairs(arr, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
public static int X = 1000000;
// Function to get all
// the prime numbers in
// the range[1, X]
public static boolean[] getPrimeNum()
{
// Stores the boolean value
// to check if a number is
// prime or not
boolean isPrime[] = new boolean[X];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
// Mark all non prime
// numbers as false
for(int i = 2; i * i <= X; i++)
{
// If i is prime number
if (isPrime[i] == true)
{
for(int j = i * i; j < X; j += i)
{
// Mark j as a composite
// number
isPrime[j] = false;
}
}
}
return isPrime;
}
// Function to get the count of pairs
// whose product is a composite number
public static int cntPairs(int arr[], int N)
{
// Stores the boolean value
// to check if a number is
// prime or not
boolean isPrime[] = getPrimeNum();
// Stores the count of 1s
int cntOne = 0;
// Stores the count
// of prime numbers
int cntPrime = 0;
// Traverse the given array.
for(int i = 0; i < N; i++)
{
if (arr[i] == 1)
{
cntOne += 1;
}
else if (isPrime[i])
{
cntPrime += 1;
}
}
// Stores count of pairs whose
// product is not a composite number
int cntNonComp = 0;
cntNonComp = cntPrime * cntOne +
cntOne * (cntOne - 1) / 2;
// Stores the count of pairs
// whose product is composite number
int res = 0;
res = N * (N - 1) / 2 - cntNonComp;
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 1, 2, 2, 8 };
int N = arr.length;
System.out.println(cntPairs(arr, N));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to implement # the above approach X = 1000000 # Function to get all # the prime numbers in # the range[1, X] def getPrimeNum(): # Stores the boolean value # to check if a number is # prime or not isPrime = [True] * (X) isPrime[0] = False isPrime[1] = False # Mark all non prime # numbers as false i = 2 while i * i <= X: # If i is prime number if (isPrime[i] == True): for j in range(i * i, X, i): # Mark j as # a composite number isPrime[j] = False i += 1 return isPrime # Function to get the count # of pairs whose product # is a composite number def cntPairs(arr, N): # Stores the boolean value # to check if a number is # prime or not isPrime = getPrimeNum() # Stores the count of 1s cntOne = 0 # Stores the count # of prime numbers cntPrime = 0 # Traverse the given array. for i in range(N): if (arr[i] == 1): cntOne += 1 elif (isPrime[i]): cntPrime += 1 # Stores count of pairs whose # product is not a composite number cntNonComp = 0 cntNonComp = (cntPrime * cntOne + cntOne * (cntOne - 1) // 2) # Stores the count of pairs # whose product is composite number res = 0 res = (N * (N - 1) // 2 - cntNonComp) return res # Driver Code if __name__ == "__main__": arr = [1, 1, 2, 2, 8] N = len(arr) print(cntPairs(arr, N)) # This code is contributed by Chitranayal
C#
// C# program to implement
// the above approach
using System;
class GFG{
public static int X = 1000000;
// Function to get all
// the prime numbers in
// the range[1, X]
public static bool[] getPrimeNum()
{
// Stores the bool value
// to check if a number is
// prime or not
bool []isPrime = new bool[X];
for(int i = 0; i < X; i++)
isPrime[i] = true;
isPrime[0] = false;
isPrime[1] = false;
// Mark all non prime
// numbers as false
for(int i = 2;
i * i <= X; i++)
{
// If i is prime number
if (isPrime[i] == true)
{
for(int j = i * i;
j < X; j += i)
{
// Mark j as a composite
// number
isPrime[j] = false;
}
}
}
return isPrime;
}
// Function to get the count of pairs
// whose product is a composite number
public static int cntPairs(int []arr,
int N)
{
// Stores the bool value
// to check if a number is
// prime or not
bool []isPrime = getPrimeNum();
// Stores the count of 1s
int cntOne = 0;
// Stores the count
// of prime numbers
int cntPrime = 0;
// Traverse the given array.
for(int i = 0; i < N; i++)
{
if (arr[i] == 1)
{
cntOne += 1;
}
else if (isPrime[i])
{
cntPrime += 1;
}
}
// Stores count of pairs
// whose product is not
// a composite number
int cntNonComp = 0;
cntNonComp = cntPrime * cntOne +
cntOne * (cntOne - 1) / 2;
// Stores the count of pairs
// whose product is composite number
int res = 0;
res = N * (N - 1) / 2 - cntNonComp;
return res;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 1, 2, 2, 8};
int N = arr.Length;
Console.WriteLine(cntPairs(arr, N));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Js program to implement
// the above approach
let X = 1000000;
// Function to get all
// the prime numbers in
// the range[1, X]
function getPrimeNum()
{
// Stores the boolean value
// to check if a number is
// prime or not
let prime = [];
for(let i = 0; i<X; i++){
prime.push(true);
}
prime[0] = false;
prime[1] = false;
for (let p = 2; p * p <= prime.length; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p]) {
// Update all multiples of p,
// set them to non-prime
for (let i = p * 2; i <= prime.length; i += p)
prime[i] = false;
}
}
return prime;
}
// Function to get the count of pairs
// whose product is a composite number
function cntPairs( arr, N)
{
// Stores the boolean value
// to check if a number is
// prime or not
let isPrime
= getPrimeNum();
// Stores the count of 1s
let cntOne = 0;
// Stores the count
// of prime numbers
let cntPrime = 0;
// Traverse the given array.
for (let i = 0; i < N; i++) {
if (arr[i] == 1) {
cntOne += 1;
}
else if (isPrime[i]) {
cntPrime += 1;
}
}
// Stores count of pairs whose
// product is not a composite number
let cntNonComp = 0;
cntNonComp = cntPrime * cntOne
+ Math.floor(cntOne * (cntOne - 1) / 2);
// Stores the count of pairs
// whose product is composite number
let res = 0;
res = N *Math.floor( (N - 1) / 2) - cntNonComp;
return res;
}
// Driver Code
let arr = [ 1, 1, 2, 2, 8 ];
let N = arr.length;
document.write( cntPairs(arr, N));
</script>
Producción
5
Complejidad de tiempo: O(N + X × log(log(X))), Donde X almacena el producto máximo posible de un par en la array dada.
Espacio Auxiliar: O(X)
Publicación traducida automáticamente
Artículo escrito por math_lover y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA