GMP

PHP5のCVS版には、gmp_nextprimeという関数が入ってるらしい。これを使うとさしずめ空中戦になるわけか。