k | PHP program to find k - th prime factor using Sieve Of Eratosthenes . This program is efficient when we have a range of numbers . ; Using SieveOfEratosthenes to find smallest prime factor of all the numbers . For example , if MAX is 10 , s [ 2 ] = s [ 4 ] = s [ 6 ] = s [ 10 ] = 2 s [ 3 ] = s [ 9 ] = 3 s [ 5 ] = 5 s [ 7 ] = 7 ; Create a boolean array " prime [ 0 . . MAX ] " and initialize all entries in it as false . ; Initializing smallest factor equal to 2 for all the even numbers ; For odd numbers less then equal to n ; s ( i ) for a prime is the number itself ; For all multiples of current prime number ; i is the smallest prime factor for number " i * j " . ; Function to generate prime factors and return its k - th prime factor . s [ i ] stores least prime factor of i . ; Keep dividing n by least prime factor while either n is not 1 or count of prime factors is not k . ; To keep track of count of prime factors ; Divide n to find next prime factor ; s [ i ] is going to store prime factor of i .
< ? php $ MAX = 10001 ; function sieveOfEratosthenes ( & $ s ) { global $ MAX ; $ prime = array_fill ( 0 , $ MAX + 1 , false ) ; for ( $ i = 2 ; $ i <= $ MAX ; $ i += 2 ) $ s [ $ i ] = 2 ; for ( $ i = 3 ; $ i <= $ MAX ; $ i += 2 ) { if ( $ prime [ $ i ] == false ) { $ s [ $ i ] = $ i ; for ( $ j = $ i ; $ j * $ i <= $ MAX ; $ j += 2 ) { if ( $ prime [ $ i * $ j ] == false ) { $ prime [ $ i * $ j ] = true ; $ s [ $ i * $ j ] = $ i ; } } } } } function kPrimeFactor ( $ n , $ k , $ s ) { while ( $ n > 1 ) { if ( $ k == 1 ) return $ s [ $ n ] ; $ k -- ; $ n = ( int ) ( $ n / $ s [ $ n ] ) ; } return -1 ; } $ s = array_fill ( 0 , $ MAX + 1 , -1 ) ; sieveOfEratosthenes ( $ s ) ; $ n = 12 ; $ k = 3 ; print ( kPrimeFactor ( $ n , $ k , $ s ) . " " ) ; $ n = 14 ; $ k = 3 ; print ( kPrimeFactor ( $ n , $ k , $ s ) ) ; ? >