Número de pasos para convertir a factores primos

Dada una array arr[] de n enteros positivos. Representa cada número como sus factores (x * y = arr[i]) [Aquí x o y no puede ser 1] hasta que no se pueda representar más como x*y = arr[i]. Imprime el número de pasos necesarios para dividirlo hasta que no sea posible realizar más representaciones.

Ejemplos: 

Input: 4 4 4
Output: 3
Explanation: 1st step 2 2 4 4 . 
             2nd step 2 2 2 2 4 
             3rd step 2 2 2 2 2 2 

Input: 20 4 
Output: 3
Explanation: 1st step 20 2 2 (2*2 = 4)
             2nd step 2 10 2 2 (2*10 = 20)
             3rd step 2 2 5 2 2, (2*5 = 10)

El enfoque es calcular previamente los factores primos de cada número. Los factores primos se pueden calcular de manera eficiente utilizando la implementación de Sieve, que requiere N * log N. . Sabemos que un número se puede representar como una multiplicación de sus factores primos y podemos representarlo hasta que no sea 1, por lo que 1 no se tiene en cuenta, por lo que si el número es distinto de 1, contamos el número de factores primos, y luego réstale 1.

Implementación:

// CPP program to count number of steps
// required to convert an integer array
// to array of factors.
#include <iostream>
using namespace std;
 
const int MAX = 1000001;
 
// array to store prime factors
int factor[MAX] = { 0 };
 
// function to generate all prime factors
// of numbers from 1 to 10^6
void cal_factor()
{
    factor[1] = 1;
 
    // Initializes all the positions with their value.
    for (int i = 2; i < MAX; i++)
        factor[i] = i;
 
    // Initializes all multiples of 2 with 2
    for (int i = 4; i < MAX; i += 2)
        factor[i] = 2;
 
    // A modified version of Sieve of Eratosthenes to
    // store the smallest prime factor that divides
    // every number.
    for (int i = 3; i * i < MAX; i++) {
 
        // check if it has no prime factor.
        if (factor[i] == i) {
 
            // Initializes of j starting from i*i
            for (int j = i * i; j < MAX; j += i) {
 
                // if it has no prime factor before, then
                // stores the smallest prime divisor
                if (factor[j] == j)
                    factor[j] = i;
            }
        }
    }
}
 
// function to calculate the number of representations
int no_of_representations(int a[], int n)
{
    // keep an count of prime factors
    int count = 0;
 
    // traverse for every element
    for (int i = 0; i < n; i++) {
 
        int temp = a[i];
        int flag = 0;
 
        // count the no of factors
        while (factor[temp] != 1) {
            flag = -1;
            count++;
            temp = temp / factor[temp];
        }
 
        // subtract 1 if Ai is not 1 as the last step
        // wont be taken into count
        count += flag;
    }
 
    return count;
}
 
// driver program to test the above function
int main()
{
    // call sieve to calculate the factors
    cal_factor();
 
    int a[] = { 4, 4, 4 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << no_of_representations(a, n);
 
    return 0;
}

// Java program to count number of steps
// required to convert an integer array
// to array of factors.
 
class GFG
{
    static final int MAX = 1000001;
 
    // array to store prime factors
    static int factor[] = new int[MAX];
 
    // function to generate all prime factors
    // of numbers from 1 to 10^6
    static void cal_factor() {
    factor[1] = 1;
 
    // Initializes all the positions
    // with their value.
    for (int i = 2; i < MAX; i++)
    factor[i] = i;
 
    // Initializes all multiples of 2 with 2
    for (int i = 4; i < MAX; i += 2)
    factor[i] = 2;
 
    // A modified version of Sieve of Eratosthenes to
    // store the smallest prime factor that divides
    // every number.
    for (int i = 3; i * i < MAX; i++) {
 
    // check if it has no prime factor.
    if (factor[i] == i) {
 
        // Initializes of j starting from i*i
        for (int j = i * i; j < MAX; j += i) {
 
        // if it has no prime factor before, then
        // stores the smallest prime divisor
        if (factor[j] == j)
            factor[j] = i;
        }
    }
    }
}
 
// function to calculate the
// number of representations
static int no_of_representations(int a[], int n) {
     
    // keep an count of prime factors
    int count = 0;
 
    // traverse for every element
    for (int i = 0; i < n; i++) {
 
    int temp = a[i];
    int flag = 0;
 
    // count the no of factors
    while (factor[temp] != 1) {
        flag = -1;
        count++;
        temp = temp / factor[temp];
    }
 
    // subtract 1 if Ai is not 1 as the
    // last step wont be taken into count
    count += flag;
    }
 
    return count;
}
 
// Driver code
public static void main(String[] args) {
     
    // call sieve to calculate the factors
    cal_factor();
 
    int a[] = {4, 4, 4};
    int n = a.length;
 
    System.out.print(no_of_representations(a, n));
}
}
 
// This code is contributed by Anant Agarwal.

# Python 3 program to count number
# of steps required to convert an
# integer array to array of factors.
MAX = 1000001
 
# array to store prime factors
factor = [0] * MAX
 
# function to generate all prime
# factors of numbers from 1 to 10^6
def cal_factor():
 
    factor[1] = 1
 
    # Initializes all the positions
    # with their value.
    for i in range(2, MAX):
        factor[i] = i
 
    # Initializes all multiples
    # of 2 with 2
    for i in range(4, MAX, 2):
        factor[i] = 2
 
    # A modified version of Sieve of
    # Eratosthenes to store the smallest
    # prime factor that divides every number.
    i = 3
    while i * i < MAX:
 
        # check if it has no prime factor.
        if (factor[i] == i) :
 
            # Initializes of j starting
            # from i*i
            for j in range(i * i, MAX, i) :
 
                # if it has no prime factor
                # before, then stores the
                # smallest prime divisor
                if (factor[j] == j):
                    factor[j] = i
                     
        i += 1
 
# function to calculate the
# number of representations
def no_of_representations(a, n):
 
    # keep an count of prime factors
    count = 0
 
    # traverse for every element
    for i in range(n) :
 
        temp = a[i]
        flag = 0
 
        # count the no of factors
        while (factor[temp] != 1) :
            flag = -1
            count += 1
            temp = temp // factor[temp]
 
        # subtract 1 if Ai is not 1 as the
        # last step wont be taken into count
        count += flag
 
    return count
 
# Driver Code
if __name__ == "__main__":
     
    # call sieve to calculate the factors
    cal_factor()
 
    a = [ 4, 4, 4 ]
    n = len(a)
 
    print(no_of_representations(a, n))
 
# This code is contributed
# by ChitraNayal

// C# program to count number of steps
// required to convert an integer array
// to array of factors.
using System;
 
class GFG {
     
    static int MAX = 1000001;
 
    // array to store prime factors
    static int []factor = new int[MAX];
 
    // function to generate all prime
    // factors of numbers from 1 to 10^6
    static void cal_factor()
    {
        factor[1] = 1;
     
        // Initializes all the positions
        // with their value.
        for (int i = 2; i < MAX; i++)
            factor[i] = i;
     
        // Initializes all multiples of
        // 2 with 2
        for (int i = 4; i < MAX; i += 2)
            factor[i] = 2;
     
        // A modified version of Sieve of
        // Eratosthenes to store the
        // smallest prime factor that
        // divides every number.
        for (int i = 3; i * i < MAX; i++)
        {
     
            // check if it has no prime
            // factor.
            if (factor[i] == i)
            {
         
                // Initializes of j
                // starting from i*i
                for (int j = i * i;
                           j < MAX; j += i)
                {
         
                    // if it has no prime
                    // factor before, then
                    // stores the smallest
                    // prime divisor
                    if (factor[j] == j)
                        factor[j] = i;
                }
            }
        }
    }
 
    // function to calculate the
    // number of representations
    static int no_of_representations(
                           int []a, int n)
    {
         
        // keep an count of prime factors
        int count = 0;
     
        // traverse for every element
        for (int i = 0; i < n; i++)
        {
            int temp = a[i];
            int flag = 0;
         
            // count the no of factors
            while (factor[temp] != 1)
            {
                flag = -1;
                count++;
                temp = temp / factor[temp];
            }
         
            // subtract 1 if Ai is not 1
            // as the last step wont be
            // taken into count
            count += flag;
        }
     
        return count;
    }
     
    // Driver code
    public static void Main()
    {
         
        // call sieve to calculate
        // the factors
        cal_factor();
     
        int []a = {4, 4, 4};
        int n = a.Length;
     
        Console.WriteLine(
            no_of_representations(a, n));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to count number of steps
// required to convert an integer array
// to array of factors.
 
$MAX = 100001;
 
// array to store prime factors
$factor = array_fill(0, $MAX + 1, 0);
 
// function to generate all prime
// factors of numbers from 1 to 10^6
function cal_factor()
{
    global $factor, $MAX;
    $factor[1] = 1;
 
    // Initializes all the positions
    // with their value.
    for ($i = 2; $i < $MAX; $i++)
        $factor[$i] = $i;
 
    // Initializes all multiples of 2 with 2
    for ($i = 4; $i < $MAX; $i += 2)
        $factor[$i] = 2;
 
    // A modified version of Sieve of
    // Eratosthenes to store the smallest
    // prime factor that divides every number.
    for ($i = 3; $i * $i < $MAX; $i++)
    {
 
        // check if it has no prime factor.
        if ($factor[$i] == $i)
        {
 
            // Initializes of j starting from i*i
            for ($j = $i * $i; $j < $MAX; $j += $i)
            {
 
                // if it has no prime factor before, then
                // stores the smallest prime divisor
                if ($factor[$j] == $j)
                    $factor[$j] = $i;
            }
        }
    }
}
 
// function to calculate the
// number of representations
function no_of_representations($a, $n)
{
    global $factor, $MAX;
     
    // keep an count of prime factors
    $count = 0;
 
    // traverse for every element
    for ($i = 0; $i < $n; $i++)
    {
 
        $temp = $a[$i];
        $flag = 0;
 
        // count the no of factors
        while ($factor[$temp] != 1) {
            $flag = -1;
            $count++;
            $temp = (int)($temp / $factor[$temp]);
        }
 
        // subtract 1 if Ai is not 1 as the
        // last step wont be taken into count
        $count += $flag;
    }
 
    return $count;
}
 
// Driver Code
 
// call sieve to calculate the factors
cal_factor();
 
$a = array( 4, 4, 4 );
$n = count($a);
 
echo no_of_representations($a, $n);
 
// This code is contributed by mits
?>

<script>
 
// Javascript program to count number of steps
// required to convert an integer array
// to array of factors.
let MAX = 1000001;
   
    // array to store prime factors
    let factor = [];
   
    // function to generate all prime factors
    // of numbers from 1 to 10^6
    function cal_factor() {
    factor[1] = 1;
   
    // Initializes all the positions
    // with their value.
    for (let i = 2; i < MAX; i++)
    factor[i] = i;
   
    // Initializes all multiples of 2 with 2
    for (let i = 4; i < MAX; i += 2)
    factor[i] = 2;
   
    // A modified version of Sieve of Eratosthenes to
    // store the smallest prime factor that divides
    // every number.
    for (let i = 3; i * i < MAX; i++) {
   
    // check if it has no prime factor.
    if (factor[i] == i) {
   
        // Initializes of j starting from i*i
        for (let j = i * i; j < MAX; j += i) {
   
        // if it has no prime factor before, then
        // stores the smallest prime divisor
        if (factor[j] == j)
            factor[j] = i;
        }
    }
    }
}
   
// function to calculate the
// number of representations
function no_of_representations(a, n) {
       
    // keep an count of prime factors
    let count = 0;
   
    // traverse for every element
    for (let i = 0; i < n; i++) {
   
    let temp = a[i];
    let flag = 0;
   
    // count the no of factors
    while (factor[temp] != 1) {
        flag = -1;
        count++;
        temp = temp / factor[temp];
    }
   
    // subtract 1 if Ai is not 1 as the
    // last step wont be taken into count
    count += flag;
    }
   
    return count;
}
     
// Driver code
 
    // call sieve to calculate the factors
    cal_factor();
   
    let a = [4, 4, 4];
    let n = a.length;
   
    document.write(no_of_representations(a, n));
     
    // This code is contributed by code_hunt.
</script>

3

Complejidad de tiempo: O(N*logN) , ya que los dos primeros bucles for que estamos usando nos costarán O(Max), luego estamos usando bucles anidados en la función cal_factor que costará usar O(Max*sqrt(Max)) y estamos utilizando bucles anidados en la función número_de_representaciones donde el bucle for externo atravesará N veces y el bucle while interno atravesará el tiempo logN y cada vez estamos disminuyendo por división de factores.

Espacio auxiliar: O(1000001) , ya que estamos usando espacio adicional para el factor.

Este artículo es una contribución de Striver . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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.