rain Вполне приличный алгоритм описан здесь: http://citeseer.ist.psu.edu/joye00efficient.html Там вообще хорошо показан путь от наивного до классического подхода. Вот здесь: http://citeseer.ist.psu.edu/186041.html есть другой интересный алгоритм - алгоритм Maurer'a, работающий по другому принципу и выдающий гарантированно простые числа. Не знаю правда, есть ли к нему уже где-нибудь рабочая реализация.
