Согласно гипотезе Крамера (она не доказано, но можете считать ее за эмпирический факт, либо очень вероятное явление), расстояние между простыми

оценивается как

- что очень мало. Поэтому можно тупо делать так: выбираете число

, возле которого ищете простое число, строите множество

проходите по нему сначала мелким решетом, а оставшееся небольшое количество простых можете тестировать на простоту уже по одному обычными алгоритмами.
Скорость алгоритма не оценивал.
до 10.000
аааа,... а я для

предлагаю

Погуглите решето Эратосфена, решето Сундарама.