The prime number distribution implicitly restricts k here. As I have mentioned above, the prime number distribution is logN, so there is no need to worry k ~ O(N), which leads to a O(N^2logN) complexity. The worst case here would be N logN loglogN.

Super Ugly Number