Multithreading and other optimization techniques are an overkill for this particular kata. I am not sure what purpose exactly the prime_numbers vector has, but the way it's processed atm causes your problems.

It looks like you're doing too many repeating calculations. Do you really need a Vec for this?

If you tell me the language I will double check, but I can assure you that tests do not go beyond signed int, which would be ~2e9, for almost all languages. Test suite is tuned to pass all tests in below 4 seconds with the almost-trivial, most basic solution (but not worse, i.e. not totally naive).

If your solution needs 800ms for a single number then it's too much, because there's 1000 numbers tested.