Number of steps to convert to prime factors | Java 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
class GFG { static final int MAX = 1000001 ; static int factor [ ] = new int [ MAX ] ; static void cal_factor ( ) { factor [ 1 ] = 1 ; for ( int i = 2 ; i < MAX ; i ++ ) factor [ i ] = i ; for ( int i = 4 ; i < MAX ; i += 2 ) factor [ i ] = 2 ; for ( int i = 3 ; i * i < MAX ; i ++ ) { if ( factor [ i ] == i ) { for ( int j = i * i ; j < MAX ; j += i ) { if ( factor [ j ] == j ) factor [ j ] = i ; } } } } static int no_of_representations ( int a [ ] , int n ) { int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int temp = a [ i ] ; int flag = 0 ; while ( factor [ temp ] != 1 ) { flag = - 1 ; count ++ ; temp = temp / factor [ temp ] ; } count += flag ; } return count ; } public static void main ( String [ ] args ) { cal_factor ( ) ; int a [ ] = { 4 , 4 , 4 } ; int n = a . length ; System . out . print ( no_of_representations ( a , n ) ) ; } }