Find maximum operations to reduce N to 1

Namachila November 19, 2025

0 0 5 minutes read

Given two numbers A and B ( A and B can be up to 10⁶ ) which forms a number N = (A!/B!). The task is to reduce N to 1 by performing maximum number of operations possible.
In each operation, one can replace N with N/X if N is divisible by X.
Find the maximum number of operations that can be possible.
Examples:

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 that factorization of number A!/B! is this same as factorization of numbers (B + 1)*(B + 2)*…*(A – 1)*A.
Also, the number of operations will be maximum if we divide N with only with it’s prime factors. So, in other words we need to find the count of prime factors of N including duplicates.
Let’s count the number of prime factors in the factorization of every number from 2 to 1000000.
First, use Sieve of Eratosthenes to find a prime divisor of each of these numbers. Then we can calculate the number of prime factors in the factorization of a using the formula:

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

Now, one can use prefix sum array for prime factors and then answer for the sum on an interval [A, B].
Below is the implementation of the above approach:

C++

// 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

// 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

# 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#

// 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
// 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
?>

Javascript

<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>

Output:

Time Complexity: O(N²)

Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!