Number of steps to convert to prime factors | Javascript 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
let MAX = 1000001 ; let factor = [ ] ; function cal_factor ( ) { factor [ 1 ] = 1 ; for ( let i = 2 ; i < MAX ; i ++ ) factor [ i ] = i ; for ( let i = 4 ; i < MAX ; i += 2 ) factor [ i ] = 2 ; for ( let i = 3 ; i * i < MAX ; i ++ ) { if ( factor [ i ] == i ) { for ( let j = i * i ; j < MAX ; j += i ) { if ( factor [ j ] == j ) factor [ j ] = i ; } } } } function no_of_representations ( a , n ) { let count = 0 ; for ( let i = 0 ; i < n ; i ++ ) { let temp = a [ i ] ; let flag = 0 ; while ( factor [ temp ] != 1 ) { flag = - 1 ; count ++ ; temp = temp / factor [ temp ] ; } count += flag ; } return count ; } cal_factor ( ) ; let a = [ 4 , 4 , 4 ] ; let n = a . length ; document . write ( no_of_representations ( a , n ) ) ;