Given two numbers A and B ( A and B can be up to 106 ) 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 numberint primeFactors[N];// Function to find number of prime// factors of each numbervoid 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 Codeint 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 possibleimport java.io.*;class GFG { static int N= 1000005;// To store number of prime// factors of each numberstatic int primeFactors[] = new int[N];// Function to find number of prime// factors of each numberstatic 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 Codepublic 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 possibleusing 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 numberfunction 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:
5
Time Complexity: O(N2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
