k | Javascript 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 .
var MAX = 10001 ; function sieveOfEratosthenes ( s ) { prime = Array . from ( { length : MAX + 1 } , ( _ , i ) => 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 /= s [ n ] ; } return - 1 ; } var s = Array . from ( { length : MAX + 1 } , ( _ , i ) => 0 ) ; sieveOfEratosthenes ( s ) ; var n = 12 , k = 3 ; document . write ( kPrimeFactor ( n , k , s ) + " " ) ; n = 14 ; k = 3 ; document . write ( kPrimeFactor ( n , k , s ) ) ;