Encuentre operaciones máximas para reducir N a 1

Dados dos números A y B (A y B pueden ser hasta 10 ⁶ ) que forman un número N = (A!/B!) . La tarea es reducir N a 1 realizando el máximo número de operaciones posible. 
En cada operación, se puede reemplazar N con N/X si N es divisible por X. 
Encuentra el número máximo de operaciones que pueden ser posibles.
Ejemplos: 
 

Input : A = 6, B = 3
Output : 5
Explanation : N is 120 and the divisors are 2, 2, 2, 3, 5

Input : A = 2, B = 1
Output : 1
Explanation : N is 2 and the divisor is 2.

Observe que la factorización del número A!/B! es lo mismo que la factorización de números (B + 1)*(B + 2)*…*(A – 1)*A.
Además, el número de operaciones será máximo si dividimos N con solo sus factores primos. Entonces, en otras palabras, necesitamos encontrar el conteo de factores primos de N, incluidos los duplicados.
Contemos el número de factores primos en la factorización de cada número desde 2 hasta 1000000.
Primero, usa la criba de Eratóstenes para encontrar un divisor primo de cada uno de estos números. Entonces podemos calcular el número de factores primos en la factorización de a usando la fórmula: 
 

primefactors[num] = primefactors[num / primediviser[num]] + 1

Ahora, uno puede usar la array de suma de prefijos para factores primos y luego responder por la suma en un intervalo [A, B].
A continuación se muestra la implementación del enfoque anterior:
 

// CPP program to find maximum
// number moves possible
 
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
 
// To store number of prime
// factors of each number
int primeFactors[N];
 
// Function to find number of prime
// factors of each number
void findPrimeFactors()
{
    for (int i = 2; i < N; i++)
        // if i is a prime number
        if (primeFactors[i] == 0)
            for (int j = i; j < N; j += i)
                // increase value by one from
                // it's previous multiple
                primeFactors[j] = primeFactors[j / i] + 1;
 
    // make prefix sum
    // this will be helpful for
    // multiple test cases
    for (int i = 1; i < N; i++)
        primeFactors[i] += primeFactors[i - 1];
}
 
// Driver Code
int main()
{
    // Generate primeFactors array
    findPrimeFactors();
 
    int a = 6, b = 3;
 
    // required answer
    cout << primeFactors[a] - primeFactors[b];
 
    return 0;
}

// Java program to find maximum
// number moves possible
import java.io.*;
 
class GFG
{
     
static int N= 1000005;
 
// To store number of prime
// factors of each number
static int primeFactors[] = new int[N];
 
// Function to find number of prime
// factors of each number
static void findPrimeFactors()
{
    for (int i = 2; i < N; i++)
     
        // if i is a prime number
        if (primeFactors[i] == 0)
            for (int j = i; j < N; j += i)
             
                // increase value by one from
                // it's previous multiple
                primeFactors[j] = primeFactors[j / i] + 1;
 
    // make prefix sum
    // this will be helpful for
    // multiple test cases
    for (int i = 1; i < N; i++)
        primeFactors[i] += primeFactors[i - 1];
}
 
// Driver Code
public static void main (String[] args)
{
 
    // Generate primeFactors array
    findPrimeFactors();
    int a = 6, b = 3;
     
    // required answer
    System.out.println (primeFactors[a] -
                        primeFactors[b]);
}
}
 
// This code is contributed by jit_t.

# Python3 program to find maximum
# number moves possible
N = 1000005
 
# To store number of prime
# factors of each number
primeFactors = [0] * N;
 
# Function to find number of prime
# factors of each number
def findPrimeFactors() :
     
    for i in range(2, N) :
         
        # if i is a prime number
        if (primeFactors[i] == 0) :
            for j in range(i, N, i) :
                 
                # increase value by one from
                # it's previous multiple
                primeFactors[j] = primeFactors[j // i] + 1;
 
    # make prefix sum this will be
    # helpful for multiple test cases
    for i in range(1, N) :
        primeFactors[i] += primeFactors[i - 1];
 
# Driver Code
if __name__ == "__main__" :
     
    # Generate primeFactors array
    findPrimeFactors();
 
    a = 6; b = 3;
 
    # required answer
    print(primeFactors[a] - primeFactors[b]);
 
# This code is contributed by Ryuga

// C# program to find maximum
// number moves possible
using System;
 
class GFG
{
    static int N = 1000005;
 
    // To store number of prime
    // factors of each number
    static int []primeFactors = new int[N];
 
    // Function to find number of prime
    // factors of each number
    static void findPrimeFactors()
    {
        for (int i = 2; i < N; i++)
     
        // if i is a prime number
        if (primeFactors[i] == 0)
            for (int j = i; j < N; j += i)
             
                // increase value by one from
                // it's previous multiple
                primeFactors[j] = primeFactors[j / i] + 1;
 
        // make prefix sum
        // this will be helpful for
        // multiple test cases
        for (int i = 1; i < N; i++)
            primeFactors[i] += primeFactors[i - 1];
    }
 
    // Driver Code
    static public void Main ()
    {
         
    // Generate primeFactors array
    findPrimeFactors();
    int a = 6, b = 3;
     
    // required answer
    Console.WriteLine(primeFactors[a] -
                        primeFactors[b]);
    }
}
 
// This code is contributed by ajit

<?php
// PHP program to find maximum
// number moves possible
 
$N = 10005;
 
// To store number of prime
// factors of each number
$primeFactors = array_fill(0, $N, 0);
 
// Function to find number of prime
// factors of each number
function findPrimeFactors()
{
    global $N,$primeFactors;
    for ($i = 2; $i < $N; $i++)
     
        // if i is a prime number
        if ($primeFactors[$i] == 0)
            for ($j = $i; $j < $N; $j += $i)
             
                // increase value by one from
                // it's previous multiple
                $primeFactors[$j] = $primeFactors[(int)($j / $i)] + 1;
 
    // make prefix sum
    // this will be helpful for
    // multiple test cases
    for ($i = 1; $i < $N; $i++)
        $primeFactors[$i] += $primeFactors[$i - 1];
}
 
    // Driver Code
     
    // Generate primeFactors array
    findPrimeFactors();
 
    $a = 6;
    $b = 3;
 
    // required answer
    print(($primeFactors[$a] - $primeFactors[$b]));
 
// This code is contributed by chandan_jnu
?>

<script>
    // Javascript program to find maximum number moves possible
     
    let N = 1000005;
   
    // To store number of prime
    // factors of each number
    let primeFactors = new Array(N);
    primeFactors.fill(0);
   
    // Function to find number of prime
    // factors of each number
    function findPrimeFactors()
    {
        for (let i = 2; i < N; i++)
       
        // if i is a prime number
        if (primeFactors[i] == 0)
            for (let j = i; j < N; j += i)
               
                // increase value by one from
                // it's previous multiple
                primeFactors[j] = primeFactors[parseInt(j / i, 10)] + 1;
   
        // make prefix sum
        // this will be helpful for
        // multiple test cases
        for (let i = 1; i < N; i++)
            primeFactors[i] += primeFactors[i - 1];
    }
     
    // Generate primeFactors array
    findPrimeFactors();
    let a = 6, b = 3;
       
    // required answer
    document.write(primeFactors[a] -
                        primeFactors[b]);
 
</script>

5

Complejidad del Tiempo: O(N ² )

Espacio Auxiliar: O(N)