O(k*(sqrt(n)/log(n) + log(n))).
hint: precalc primes table(so, we can factorize number using O(sqrt(N)/log(N)) operations).
gl.