thoughts on a multithreaded version

[teub]

O(1) is great but what if I have more than 1 core, is there any way of making use of them as well ?

I thought about duplicating the code is_prime_1() is_prime_2()... is_prime_n(), n being the number of cores, but that doesn't sound very optimized. I'm afraid of potential racing conditions as well.

Anyway the multithread question led me to wonder if your original code could maybe even be further optimized, let me know if I should open a separate issue :
another approach completely would be to have one function per number to test; instead of calling is_prime(42), you would call is_prime_42() { return false; }.
It's slightly less convenient than calling is_prime(42) because you need to have a switch case on the value, but it has one less parameter so it sounds like it should be faster for each call what do you think.

[Acters]

You can set each core to only handle multiples of each number except for multiples of 1. This way you can cover almost all the numbers. while having one core handle the numbers skipped by your other cores. probable max multithreaded efficiency use case will be to have about 10 cores dedicated to crunching numbers, after that multithreading will be too complicated to work.

This way you have one core handling any missed numbers, then second core handling multiples of 2, third core handling multiples of 3, fourth core handling multiples of 4, …and so on... up to core nine handling multiples of 9. This way all numbers get tested. Unfortunately some numbers will be tested more than once by different cores.

[Acters]

your worries of A race condition occurring will only be problematic when two or more threads that can access shared data and try to change it at the same time to different values. This does not need to be a problem as both threads should come to the same conclusion/write the same value.

[yoifox]

cuda implementation uses more than 1000000 threads