Задействовать сигналы для связи между потоками кажется избыточным. В этом случае я бы использовал ожидание на condition variable.
condition_variable::wait
и condition_variable::notify_one
работают? Да даже этот интерфейс изоморфен WaitForSingleObject/SetEvent.
Конкретно в этом примере использование атомиков в сочетании с yieldом для синхронизации потоков будет самым дешевым, на мой взгляд
Ну и, да, надо commit базе делать почаще, а не в самом конце (допустим, каждые 100 найденных чисел, или каждые 1000 итераций внутреннего цикла, или как-то еще)
Разбивать интервал на маленькие интервалы и рассматривать их отдельно нельзя - вы теряете решения, где числа в разных интервалах.