All multiples of i are composite ( and divisible by i ) so add i to their prime factorization getpow ( j , i ) times
for ( int j = i * i ; j < n + 1 ; j += i ) if ( SPF [ j ] == j ) { SPF [ j ] = i ; } } }