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

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

какой же алгоритм мне реализовать?