Dada una array de enteros. Encuentre el número total de subarreglos cuyo producto de todos los elementos no contiene un factor primo que se repite en la descomposición en primos del número resultante.
Ejemplos:
Input: 2 3 9
Output: 3
Explanation:
Total sub-array are:-
{2}, {3}, {9}, {2, 3}, {3, 9}, {2, 3, 9}
Subarray which violets the property are:-
{9} -> {3 * 3}, Since 3 is a repeating prime
factor in prime decomposition of 9
{3, 9} -> {3 * 3 * 3}, 3 is a repeating prime
factor in prime decomposition of 27
{2, 3, 9} -> {2 * 3 * 3 * 3}, 3 is repeating
prime factor in prime decomposition
of 54
Hence total subarray remains which satisfies our
condition are 3.
Input: 2, 3, 5, 15, 7, 2
Output: 12
Un enfoque ingenuo es ejecutar un bucle uno dentro de otro y generar todos los subarreglos y luego tomar el producto de todos los elementos de modo que su descomposición principal no contenga elementos repetidos. Este enfoque definitivamente sería lento y conduciría a un desbordamiento de gran valor del elemento de array.
Un enfoque eficiente es utilizar la descomposición en factores primos mediante la criba de Eratóstenes.
La idea es almacenar el factor primo más pequeño (SPF) para todos los valores (hasta un máximo) usando Sieve . Calculamos la descomposición en factores primos del número dado dividiendo recursivamente el número dado con su factor primo más pequeño hasta que se convierte en 1.
- Sea ind[] una array tal que ind[i] almacena el último índice del divisor primo i en arr[], y ‘last_ind’ realiza un seguimiento del último índice de cualquier divisor.
- Ahora recorra de izquierda a derecha (0 a n-1). Para un elemento particular de array[i], busque divisores primos usando el enfoque anterior e inicialice todos los divisores con el último índice ‘i+1’ .
- Pero antes de realizar el paso 2, actualizamos la variable de ‘last_ind’ con ind[] de cada divisor de array[i].
- Dado que la variable ‘last_ind’ contiene un último índice (menor que i) de cualquier divisor de array[i], podemos asegurar que todos los elementos (last_ind+1, last_ind+2 … i) no tendrán ningún factor primo repetitivo de arr [i]. Por lo tanto, nuestra respuesta será (i – last_ind +1)
- Realice los pasos anteriores para el elemento restante de la array [] y actualice simultáneamente la respuesta para cada índice.
Implementación:
C++
// C++ program to count all sub-arrays whose
// product doesn't contain a repeating prime
// factor.
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000001;
int spf[MAXN];
// Calculating SPF (Smallest Prime Factor) for
// every number till MAXN.
// Time Complexity : O(n log log n)
void sieve()
{
// marking smallest prime factor for every
// number to be itself.
for (int i=1; i<MAXN; i++)
spf[i] = i;
// separately marking spf for every even
// number as 2
for (int i=4; i<MAXN; i+=2)
spf[i] = 2;
for (int i=3; i*i<MAXN; i++)
{
// checking if i is prime
if (spf[i] == i)
{
// marking SPF for all numbers divisible
// by i
for (int j=i*i; j<MAXN; j+=i)
// marking spf[j] if it is not
// previously marked
if (spf[j]==j)
spf[j] = i;
}
}
}
// Function to count all sub-arrays whose
// product doesn't contain a repeating prime
// factor.
int countSubArray(int arr[], int n)
{
// ind[i] is going to store 1 + last index of
// of an array element which has i as prime
// factor.
int ind[MAXN];
memset(ind, -1, sizeof ind);
int count = 0; // Initialize result
int last_ind = 0; // It stores index
for (int i=0; i < n; ++i)
{
while (arr[i] > 1)
{
int div = spf[arr[i]];
// Fetch the last index of prime
// divisor of element
last_ind = max(last_ind, ind[div]);
// Update the current divisor index
ind[div] = i + 1;
arr[i] /= div;
}
// Update result, we basically include
// all required subarrays ending with
// index arr[i].
count += i - last_ind + 1;
}
return count;
}
// Driver code
int main()
{
sieve();
int arr[] = {2, 3, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout << countSubArray(arr, n) << "\n";
int arr1[] = {2, 3, 5, 15, 7, 2};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
cout << countSubArray(arr1, n1);
return 0;
}
Java
// Java program to count all sub-arrays whose
// product doesn't contain a repeating prime
// factor
import java.io.*;
import java.util.*;
class GFG
{
public static int MAXN = 1000001;
public static int[] spf = new int[MAXN];
// Calculating SPF (Smallest Prime Factor) for
// every number till MAXN.
// Time Complexity : O(n log log n)
static void sieve()
{
// marking smallest prime factor for every
// number to be itself.
for (int i=1; i<MAXN; i++)
spf[i] = i;
// separately marking spf for every even
// number as 2
for (int i=4; i<MAXN; i+=2)
spf[i] = 2;
for (int i=3; i*i<MAXN; i++)
{
// checking if i is prime
if (spf[i] == i)
{
// marking SPF for all numbers divisible
// by i
for (int j=i*i; j<MAXN; j+=i)
// marking spf[j] if it is not
// previously marked
if (spf[j]==j)
spf[j] = i;
}
}
}
// Function to count all sub-arrays whose
// product doesn't contain a repeating prime
// factor
static int countSubArray(int arr[], int n)
{
// ind[i] is going to store 1 + last index of
// of an array element which has i as prime
// factor.
int[] ind = new int[MAXN];
Arrays.fill(ind, -1);
int count = 0; // Initialize result
int last_ind = 0; // It stores index
for (int i=0; i < n; ++i)
{
while (arr[i] > 1)
{
int div = spf[arr[i]];
// Fetch the last index of prime
// divisor of element
last_ind = Math.max(last_ind, ind[div]);
// Update the current divisor index
ind[div] = i + 1;
arr[i] /= div;
}
// Update result, we basically include
// all required subarrays ending with
// index arr[i].
count += i - last_ind + 1;
}
return count;
}
// driver program
public static void main (String[] args)
{
sieve();
int arr[] = {2, 3, 9};
int n = arr.length;
System.out.println(countSubArray(arr, n));
int arr1[] = {2, 3, 5, 15, 7, 2};
int n1 = arr1.length;
System.out.println(countSubArray(arr1, n1));
}
}
// Contributed by Pramod Kumar
Python3
# Python 3 program to count all sub-arrays # whose product does not contain a repeating # prime factor. from math import sqrt MAXN = 1000001 spf = [0 for i in range(MAXN)] # Calculating SPF (Smallest Prime Factor) # for every number till MAXN. # Time Complexity : O(n log log n) def sieve(): # marking smallest prime factor # for every number to be itself. for i in range(1, MAXN, 1): spf[i] = i # separately marking spf for # every even number as 2 for i in range(4, MAXN, 2): spf[i] = 2 k = int(sqrt(MAXN)) for i in range(3, k, 1): # checking if i is prime if (spf[i] == i): # marking SPF for all numbers # divisible by i for j in range(i * i, MAXN, i): # marking spf[j] if it is # not previously marked if (spf[j] == j): spf[j] = i # Function to count all sub-arrays whose # product doesn't contain a repeating # prime factor. def countSubArray(arr, n): # ind[i] is going to store 1 + last # index of an array element which # has i as prime factor. ind = [-1 for i in range(MAXN)] count = 0 # Initialize result last_ind = 0 # It stores index for i in range(0, n, 1): while (arr[i] > 1): div = spf[arr[i]] # Fetch the last index of prime # divisor of element last_ind = max(last_ind, ind[div]) # Update the current divisor index ind[div] = i + 1 arr[i] = int(arr[i] / div) # Update result, we basically include # all required subarrays ending with # index arr[i]. count += i - last_ind + 1 return count # Driver code if __name__ == '__main__': sieve() arr = [2, 3, 9] n = len(arr) print(countSubArray(arr, n)) arr1 = [2, 3, 5, 15, 7, 2] n1 = len(arr1) print(countSubArray(arr1, n1)) # This code is contributed by # Shashank_Sharma
C#
// C# program to count all sub-arrays
// whose product doesn't contain a
// repeating prime factor
using System;
public class GFG {
public static int MAXN = 1000001;
public static int[] spf = new int[MAXN];
// Calculating SPF (Smallest Prime Factor)
// for every number till MAXN.
// Time Complexity : O(n log log n)
static void sieve()
{
// marking smallest prime factor
// for every number to be itself.
for (int i = 1; i < MAXN; i++)
spf[i] = i;
// separately marking spf for
// every even number as 2
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++)
{
// checking if i is prime
if (spf[i] == i)
{
// marking SPF for all numbers divisible
// by i
for (int j = i * i; j < MAXN; j += i)
// marking spf[j] if it is
// not previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to count all sub-arrays
// whose product doesn't contain
// a repeating prime factor
static int countSubArray(int []arr, int n)
{
// ind[i] is going to store 1 + last
// index of an array element which
// has i as prime factor.
int[] ind = new int[MAXN];
for(int i = 0; i < MAXN; i++)
{
ind[i] = -1;
}
int count = 0; // Initialize result
int last_ind = 0; // It stores index
for (int i = 0; i < n; ++i)
{
while (arr[i] > 1)
{
int div = spf[arr[i]];
// Fetch the last index of prime
// divisor of element
last_ind = Math.Max(last_ind, ind[div]);
// Update the current divisor index
ind[div] = i + 1;
arr[i] /= div;
}
// Update result, we basically include
// all required subarrays ending with
// index arr[i].
count += i - last_ind + 1;
}
return count;
}
// Driver Code
public static void Main ()
{
sieve();
int []arr = {2, 3, 9};
int n = arr.Length;
Console.WriteLine(countSubArray(arr, n));
int []arr1 = {2, 3, 5, 15, 7, 2};
int n1 = arr1.Length;
Console.WriteLine(countSubArray(arr1, n1));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to count all sub-arrays whose
// product doesn't contain a repeating prime
// factor.
$MAXN = 1000001;
$spf = array_fill(0, $MAXN, NULL);
// Calculating SPF (Smallest Prime Factor)
// for every number till MAXN.
// Time Complexity : O(n log log n)
function sieve()
{
global $spf, $MAXN;
// marking smallest prime factor for
// every number to be itself.
for ($i = 1; $i < $MAXN; $i++)
$spf[$i] = $i;
// separately marking spf for every
// even number as 2
for ($i = 4; $i < $MAXN; $i += 2)
$spf[$i] = 2;
for ($i = 3; $i * $i < $MAXN; $i++)
{
// checking if i is prime
if ($spf[$i] == $i)
{
// marking SPF for all numbers
// divisible by i
for ($j = $i * $i; $j < $MAXN; $j += $i)
// marking spf[j] if it is not
// previously marked
if ($spf[$j] == $j)
$spf[$j] = $i;
}
}
}
// Function to count all sub-arrays whose
// product doesn't contain a repeating
// prime factor.
function countSubArray(&$arr, $n)
{
global $MAXN, $spf;
// ind[i] is going to store 1 + last index
// of an array element which has i as prime
// factor.
$ind = array_fill(-1, $MAXN, NULL);
$count = 0; // Initialize result
$last_ind = 0; // It stores index
for ($i = 0; $i < $n; ++$i)
{
while ($arr[$i] > 1)
{
$div = $spf[$arr[$i]];
// Fetch the last index of prime
// divisor of element
$last_ind = max($last_ind, $ind[$div]);
// Update the current divisor index
$ind[$div] = $i + 1;
if($div != 0)
$arr[$i] /= $div;
}
// Update result, we basically include
// all required subarrays ending with
// index arr[i].
$count += $i - $last_ind + 1;
}
return $count;
}
// Driver code
sieve();
$arr = array(2, 3, 9);
$n = sizeof($arr);
echo countSubArray($arr, $n) . "\n";
$arr1 = array(2, 3, 5, 15, 7, 2);
$n1 = sizeof($arr1);
echo countSubArray($arr1, $n1);
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to count all sub-arrays whose
// product doesn't contain a repeating prime
// factor
let MAXN = 1000001;
let spf = new Array(MAXN);
// Calculating SPF (Smallest Prime Factor) for
// every number till MAXN.
// Time Complexity : O(n log log n)
function sieve()
{
// marking smallest prime factor for every
// number to be itself.
for (let i = 1; i < MAXN; i++)
spf[i] = i;
// separately marking spf for every even
// number as 2
for (let i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (let i = 3; i * i < MAXN; i++)
{
// checking if i is prime
if (spf[i] == i)
{
// marking SPF for all numbers divisible
// by i
for (let j = i * i; j < MAXN; j += i)
// marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to count all sub-arrays whose
// product doesn't contain a repeating prime
// factor
function countSubArray(arr,n)
{
// ind[i] is going to store 1 + last index of
// of an array element which has i as prime
// factor.
let ind = new Array(MAXN);
for(let i = 0; i < ind.length; i++)
{
ind[i] = -1;
}
let count = 0; // Initialize result
let last_ind = 0; // It stores index
for (let i = 0; i < n; ++i)
{
while (arr[i] > 1)
{
let div = spf[arr[i]];
// Fetch the last index of prime
// divisor of element
last_ind = Math.max(last_ind, ind[div]);
// Update the current divisor index
ind[div] = i + 1;
arr[i] /= div;
}
// Update result, we basically include
// all required subarrays ending with
// index arr[i].
count += i - last_ind + 1;
}
return count;
}
// driver program
sieve();
let arr = [2, 3, 9];
let n = arr.length;
document.write(countSubArray(arr, n)+"<br>");
let arr1 = [2, 3, 5, 15, 7, 2];
let n1 = arr1.length;
document.write(countSubArray(arr1, n1));
// This code is contributed by rag2127
</script>
Producción
3 12
Complejidad del tiempo: O(MAX*log(log(MAX) + nlog(n))
Espacio auxiliar: O(MAX)
Este artículo es una contribución de Shubham Bansal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA