[Solved] finding number of numbers which have prime number of factors

You could try computing this mathematically (I’m not sure this will be faster/easier). Basically, given the prime factorization of a number, you should be able to calculate the number of divisors without too much trouble.

If you have an input x decompose into something like

x = p1^a1 * p2^a2 * ... pn^an

Then the number of divisors should be

prod(ai + 1) for i in 1 to n

I would then look at finding the smallest prime < sqrt(x), dividing that out until you’re left with just a prime. A sieve might still be useful and I don’t know what kind of input you would be getting.

Now consider what the above statement says: the number of divisors in the product of the powers of the prime factorization (plus 1). Thus, if you only every care if the result is prime, then you should only ever consider numbers which are prime, or powers of primes. And within that, you then only need to consider powers such that a1 + 1 is prime.

That should significantly cut down your search space.