PE 0007
・問題リンクFind the 10001st prime.
・コメント
自分でこのコーディングは思いつきませんでした(笑)
ですが、ソースを読んでなるほどとなりましたね。
ポイントは偶数は2以外は間違いなく素数ではないので判断対象をまず奇数に絞り込み、更に、、素数であるかの判断対象の数を割っていく数は素数のみを考えればよく(素数以外の数で割る必要はない)、更にさらに、その数の平方根以下の数で割れるかを判断すればいい(例えば、11が素数であるかの判定をする場合、まず、最初の割る数2のパターンを考える。11>2*2である。割る数の二乗はその数自体で割ることができるため、考えればいいのは対象の数(割る数)の平方根以下だけを考えればいいという事だと思います←)。
・ソース
public class P0007 { public static void main(String[] args) { int primeCounter = 0;// 素数の数 int[] primeBox = new int[10100];// 素数を格納する箱 primeBox[primeCounter++] = 2;// 素数2と primeBox[primeCounter++] = 3;// 素数3を登録 for (int n = 5; primeCounter < 10002; n += 2) {// 奇数のみ判定対象 boolean flag = false;// 割り切れたか for (int i = 1; primeBox[i] * primeBox[i] <= n; i++) {// 対象数の平方根以下のすべての素数で除算する if (n % primeBox[i] == 0) {// 割り切れたら素数ではない flag = true; break; } } if (flag == false) {// 最後まで割り切れなかったら primeBox[primeCounter++] = n; } } System.out.println(primeBox[10000]); } }