>665
「エラトステネスのふるい」というアルゴリズムが一般的。
検索すると多分大量に見つかる。
sqrt(n)の倍数までを弾けば残りは素数である事が保証される事に注意。