Нахождение простых чисел (pascal)

Question

Нужно реализовать на Delphi 7 алгоритм нахождения простых чисел. 
Особенность заключается в том, что нужно найти лишь первое простое число, следующее за числом N(0<=N<=4000000000). При этом, количество таких тестов может доходить до тысячи за раз (со случайными числами) Решета Эратосфена и Аткинса никак не пойдут, а работа программы должна укладываться в секунду. Пробовал также использовать базу простых чисел (2~63247), но получался слишком громадный код (система проверки не принимала) . 
 
какой же алгоритм мне реализовать?

kuzyak_v · Accepted Answer

sqrt(4e9) - где-то 64000. Если проверять только числа вида 6n±1, получится 21300 проверок. Если 1000 чисел в секунду - будет 21 млн. делений. На 2ГГц процессоре может получиться.