Function to precompute shortest prime factors
function sieve ( ) { for ( var i = 0 ; i < 100005 ; i ++ ) spf [ i ] = - 1 ; for ( var i = 2 ; i * i <= 100005 ; i ++ ) { for ( var j = i ; j <= 100005 ; j += i ) { if ( spf [ j ] == - 1 ) { spf [ j ] = i ; } } } }