Isn't this kata too easy for 5 kyu? Or is it just for Python (where the solution takes one line), and it's much harder in other languages?

Nice, but is it worth 4 kyu? :) This kata is very straightforward, and you almost don't need to think, just implement what's written in the description.

Can anyone tell me if implementing specific factorization algorithm like Quadratic sieve is essential for this kata? I have a feeling that factorization is the bottleneck, but maybe I'm mistaken.

(I'm not sure if this question is a spoiler, as it's not that far from what is written in the article linked in the kata's description :)