Find all Factors of Large Perfect Square Natural Number in O ( sqrt ( sqrt ( N ) ) | Javascript program to find the factors of large perfect square number in O ( Math . sqrt ( Math . sqrt ( N ) ) ) time ; Function that find all the prime factors of N ; Store the Math . sqrt ( N ) in temp ; Initialise factor array with 1 as a factor in it ; Check divisibility by 2 ; Store the factors twice ; Check for other prime factors other than 2 ; If j is a prime factor ; Store the prime factor twice ; If j is prime number left other than 2 ; Store j twice ; Initialise Matrix M to to store all the factors ; tpc for rows tpr for column ; Initialise M [ 0 ] [ 0 ] = 1 as it also factor of N ; Traversing factor array ; If current and previous factors are not same then move to next row and insert the current factor ; If current and previous factors are same then , Insert the factor with previous factor inserted in matrix M ; The arr1 [ ] and arr2 [ ] used to store all the factors of N ; Initialise arrays as 1 ; Traversing the matrix M ; Traversing till column element doesn 't become 0 ; Store the product of every element of current row with every element in arr1 [ ] ; Copying every element of arr2 [ ] in arr1 [ ] ; length of arr2 [ ] and arr1 [ ] are equal after copying ; Print all the factors ; Driver Code
let MAX = 100000 ; function findFactors ( N ) { let temp = Math . floor ( Math . sqrt ( N ) ) ; let factor = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) { factor [ i ] = 1 ; } let i , j , k ; let len1 = 1 ; while ( temp % 2 == 0 ) { factor [ len1 ++ ] = 2 ; factor [ len1 ++ ] = 2 ; temp = Math . floor ( temp / 2 ) ; } for ( j = 3 ; j < Math . sqrt ( temp ) ; j += 2 ) { while ( temp % j == 0 ) { factor [ len1 ++ ] = j ; factor [ len1 ++ ] = j ; temp = Math . floor ( temp / j ) ; } } if ( temp > 2 ) { factor [ len1 ++ ] = temp ; factor [ len1 ++ ] = temp ; } let M = new Array ( len1 ) ; for ( let i = 0 ; i < len1 ; i ++ ) { M [ i ] = new Array ( MAX ) ; for ( let j = 0 ; j < MAX ; j ++ ) { M [ i ] [ j ] = 0 ; } } let tpc = 0 , tpr = 0 ; M [ 0 ] [ 0 ] = 1 ; j = 1 ; while ( j < len1 ) { if ( factor [ j ] != factor [ j - 1 ] ) { tpr ++ ; M [ tpr ] [ 0 ] = factor [ j ] ; j ++ ; tpc = 1 ; } else { M [ tpr ] [ tpc ] = M [ tpr ] [ tpc - 1 ] * factor [ j ] ; j ++ ; tpc ++ ; } } let arr1 = new Array ( MAX ) ; let arr2 = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) { arr1 [ i ] = 0 ; arr2 [ i ] = 0 ; } let l1 , l2 ; l1 = l2 = 1 ; arr1 [ 0 ] = arr2 [ 0 ] = 1 ; for ( i = 1 ; i < tpr + 1 ; i ++ ) { for ( j = 0 ; M [ i ] [ j ] != 0 ; j ++ ) { for ( k = 0 ; k < l1 ; k ++ ) { arr2 [ l2 ++ ] = arr1 [ k ] * M [ i ] [ j ] ; } } for ( j = l1 ; j < l2 ; j ++ ) { arr1 [ j ] = arr2 [ j ] ; } l1 = l2 ; } for ( i = 0 ; i < l2 ; i ++ ) { document . write ( arr2 [ i ] + " " ) ; } } let N = 900 ; findFactors ( N ) ;