Find all Factors of Large Perfect Square Natural Number in O ( sqrt ( sqrt ( N ) ) | Java 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 ; Drivers Code
import java . util . * ; class GFG { static int MAX = 100000 ; static void findFactors ( int N ) { int temp = ( int ) Math . sqrt ( N ) ; int [ ] factor = new int [ MAX ] ; Arrays . fill ( factor , 1 ) ; int i , j , k ; int len1 = 1 ; while ( temp % 2 == 0 ) { factor [ len1 ++ ] = 2 ; factor [ len1 ++ ] = 2 ; temp /= 2 ; } for ( j = 3 ; j < Math . sqrt ( temp ) ; j += 2 ) { while ( temp % j == 0 ) { factor [ len1 ++ ] = j ; factor [ len1 ++ ] = j ; temp /= j ; } } if ( temp > 2 ) { factor [ len1 ++ ] = temp ; factor [ len1 ++ ] = temp ; } int [ ] [ ] M = new int [ len1 ] [ MAX ] ; int 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 ++ ; } } int [ ] arr1 = new int [ MAX ] ; int [ ] arr2 = new int [ MAX ] ; int 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 ++ ) { System . out . print ( arr2 [ i ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int N = 900 ; findFactors ( N ) ; } }