Find maximum operations to reduce N to 1 | PHP 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 ; Generate primeFactors array ; required answer
< ? php $ N = 10005 ; $ primeFactors = array_fill ( 0 , $ N , 0 ) ; function findPrimeFactors ( ) { global $ N , $ primeFactors ; for ( $ i = 2 ; $ i < $ N ; $ i ++ ) if ( $ primeFactors [ $ i ] == 0 ) for ( $ j = $ i ; $ j < $ N ; $ j += $ i ) $ primeFactors [ $ j ] = $ primeFactors [ ( int ) ( $ j / $ i ) ] + 1 ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) $ primeFactors [ $ i ] += $ primeFactors [ $ i - 1 ] ; } findPrimeFactors ( ) ; $ a = 6 ; $ b = 3 ; print ( ( $ primeFactors [ $ a ] - $ primeFactors [ $ b ] ) ) ; ? >