Prime Factorization using Sieve O ( log n ) for multiple queries | PHP program to find prime factorization of a number n in O ( Log n ) time with precomputation allowed . ; stores smallest prime factor for every number ; Calculating SPF ( Smallest Prime Factor ) for every number till MAXN . Time Complexity : O ( nloglogn ) ; marking smallest prime factor for every number to be itself . ; separately marking spf for every even number as 2 ; checking if i is prime ; marking SPF for all numbers divisible by i ; marking spf [ j ] if it is not previously marked ; A O ( log n ) function returning primefactorization by dividing by smallest prime factor at every step ; precalculating Smallest Prime Factor ; calling getFactorization function
< ? php $ MAXN = 19999 ; $ spf = array_fill ( 0 , $ MAXN , 0 ) ; function sieve ( ) { global $ MAXN , $ spf ; $ spf [ 1 ] = 1 ; for ( $ i = 2 ; $ i < $ MAXN ; $ i ++ ) $ spf [ $ i ] = $ i ; for ( $ i = 4 ; $ i < $ MAXN ; $ i += 2 ) $ spf [ $ i ] = 2 ; for ( $ i = 3 ; $ i * $ i < $ MAXN ; $ i ++ ) { if ( $ spf [ $ i ] == $ i ) { for ( $ j = $ i * $ i ; $ j < $ MAXN ; $ j += $ i ) if ( $ spf [ $ j ] == $ j ) $ spf [ $ j ] = $ i ; } } } function getFactorization ( $ x ) { global $ spf ; $ ret = array ( ) ; while ( $ x != 1 ) { array_push ( $ ret , $ spf [ $ x ] ) ; if ( $ spf [ $ x ] ) $ x = ( int ) ( $ x / $ spf [ $ x ] ) ; } return $ ret ; } sieve ( ) ; $ x = 12246 ; echo " prime ▁ factorization ▁ for ▁ " . $ x . " ▁ : ▁ " ; $ p = getFactorization ( $ x ) ; for ( $ i = 0 ; $ i < count ( $ p ) ; $ i ++ ) echo $ p [ $ i ] . " ▁ " ; ? >