素数の求め方について

Question

「"０～１００"までの素数を表示するプログラム」をJavaで作成しようとしています。

こちらのサイトを参考にプログラムを作成したら、無事プログラムをつくることができたのですが、素数を求める処理の中で、１点わからないことがあります。

 public static void main(String[] args){
  boolean f; //素数ならtrue
      for(int i = 2; i<=100; i ++){
        f = true;
        for (int j = 2; j < i/2; j++) { //割れたら素数ではない。なぜ「i/2」なのか？
          if (i % j == 0) {
            f = false;
            break;
          }          
        } 
        if(f) {
          System.out.println(i + " ");
        }
      }
   }
}

上記のプログラムでは、iは素数か判定したい数（割られる数）、jは素数判定するための割る数である、というところまでは理解できます。

ここで、なぜ、iが素数なのかを確かめるために、「j<i/2」までfor文を回すことになるのでしょうか？
「約数が 1 と自分自身のみの数かどうか」を確かめるためには、割る数であるjが「j<i」の場合まで割ってみて判定する必要があるように思うのですが（実際「j<i」でもプログラムは正しく動きます）、「j<i/2」でもプログラムは正しく素数を判定しています。

どういう理屈でそうなっているのでしょうか・・・？

プログラムの問題というより数学的な理屈の問題で恐縮なのですが、よろしくお願いいたします。

Answer 1

これは算数の範疇の話ですね。
iが、i/2以上の数xで割り切れたら、その商yはi/2より小さいです。
i/2以上の数を2つ掛けると、必ずその積はiより大きいです。
（正確にはこれが成り立つのはiが4以上の場合ですが、2や3は素数なので関係ない）

なので、小さい方から順に割ってけば、xより先にyで割り切れるのでそこで終わりです。
なお、i/2まで調べる必要もなくて、iの平方根まで調べれば十分なので、普通は平方根まで調べます。

Comments

[moritat-222]

iがi/2以上の数で割れるならば、その商は必ずi/2より小さいので、iが商だった時にもう判定されているはず
（例えばi=28なら、j=14まで調べなくとも、j=2の時点で割り切れると判明している）ということですね。
スッキリしました。
ありがとうございます！

[swordone]

削除

Answer 2

17が素数かどうかを判定したいとき、半分の8まで調べれば十分ですよね。検査対象の半分超の数で割り切れることはない。

Comments

[Zuishin]

25 が素数かどうかを判定したい時、半分の 12 ではなく 5 まで調べれば十分です。

[otn]

半分まで調べることが必要と言ってるわけじゃないので、間違ってはいないので、低評価はおかしいな。

[shiketa]

問いが
> なぜ、iが素数なのかを確かめるために、「j<i/2」までfor文を回すことになるのでしょうか？
だったのよ。

[Zuishin]

j<i/2 まで回す必要はないので、「回すこと」にはならないのよ。
低評価がおかしいなら高評価すればいいのでは？