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