Number of steps to convert to prime factors | Python 3 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 ; Driver Code ; call sieve to calculate the factors
MAX = 1000001 NEW_LINE factor = [ 0 ] * MAX NEW_LINE def cal_factor ( ) : NEW_LINE INDENT factor [ 1 ] = 1 NEW_LINE for i in range ( 2 , MAX ) : NEW_LINE INDENT factor [ i ] = i NEW_LINE DEDENT for i in range ( 4 , MAX , 2 ) : NEW_LINE INDENT factor [ i ] = 2 NEW_LINE DEDENT i = 3 NEW_LINE while i * i < MAX : NEW_LINE INDENT if ( factor [ i ] == i ) : NEW_LINE INDENT for j in range ( i * i , MAX , i ) : NEW_LINE INDENT if ( factor [ j ] == j ) : NEW_LINE INDENT factor [ j ] = i NEW_LINE DEDENT DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT def no_of_representations ( a , n ) : NEW_LINE INDENT count = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT temp = a [ i ] NEW_LINE flag = 0 NEW_LINE while ( factor [ temp ] != 1 ) : NEW_LINE INDENT flag = - 1 NEW_LINE count += 1 NEW_LINE temp = temp // factor [ temp ] NEW_LINE DEDENT count += flag NEW_LINE DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT cal_factor ( ) NEW_LINE a = [ 4 , 4 , 4 ] NEW_LINE n = len ( a ) NEW_LINE print ( no_of_representations ( a , n ) ) NEW_LINE DEDENT