Number of steps to convert to prime factors | PHP program to count number of steps required to convert an integer array to array of factors . ; array to store prime factors ; function to generate all prime factors of numbers from 1 to 10 ^ 6 ; Initializes all the positions with their value . ; Initializes all multiples of 2 with 2 ; A modified version of Sieve of Eratosthenes to store the smallest prime factor that divides every number . ; check if it has no prime factor . ; Initializes of j starting from i * i ; if it has no prime factor before , then stores the smallest prime divisor ; function to calculate the number of representations ; keep an count of prime factors ; traverse for every element ; count the no of factors ; subtract 1 if Ai is not 1 as the last step wont be taken into count ; call sieve to calculate the factors
< ? php $ MAX = 100001 ; $ factor = array_fill ( 0 , $ MAX + 1 , 0 ) ; function cal_factor ( ) { global $ factor , $ MAX ; $ factor [ 1 ] = 1 ; for ( $ i = 2 ; $ i < $ MAX ; $ i ++ ) $ factor [ $ i ] = $ i ; for ( $ i = 4 ; $ i < $ MAX ; $ i += 2 ) $ factor [ $ i ] = 2 ; for ( $ i = 3 ; $ i * $ i < $ MAX ; $ i ++ ) { if ( $ factor [ $ i ] == $ i ) { for ( $ j = $ i * $ i ; $ j < $ MAX ; $ j += $ i ) { if ( $ factor [ $ j ] == $ j ) $ factor [ $ j ] = $ i ; } } } } function no_of_representations ( $ a , $ n ) { global $ factor , $ MAX ; $ count = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ temp = $ a [ $ i ] ; $ flag = 0 ; while ( $ factor [ $ temp ] != 1 ) { $ flag = -1 ; $ count ++ ; $ temp = ( int ) ( $ temp / $ factor [ $ temp ] ) ; } $ count += $ flag ; } return $ count ; } cal_factor ( ) ; $ a = array ( 4 , 4 , 4 ) ; $ n = count ( $ a ) ; echo no_of_representations ( $ a , $ n ) ; ? >