##素数を判定するアルゴリズムについて

例: 101が素数か判定するにあたって 1 -100すべてで割る（グリーディーなアルゴリズム）必要がありません

(int) sqrt(101) = 10 を越えない素数 2,3,5,7だけでチェックすればいいというのが答えです　
エラトステネスのふるいとかいう魔法みたいな言葉はよくわからんでいいです

何故かについては下記理由となります

####理由1 平方根以下の数で探せばよい理由

101が10以上の数で割れるとした場合（19とかで割れるとしましょう）

101 = 19 x (相方となる数）がいます

そう考えると、この相方は101の平方根より小さくなるはずです、19で割れると同時に相方でも割れるはずですが、相方は19より先に出てきているはずです。そんな感じで相方のことを常に考えていくと、平方根以下で探せばよいことがわかります

####理由2　素数以外の数＝合成数(例14）で割る必要がない理由

101が「1 -100すべてで割る」で、例えば頑張って1-14まで探してようやく14で割れるとした場合を仮定するとこれはあり得ません。14は素因数分解すると2x7なので、14で割れるとしたら14より先に出てくる2,7の時点ですでに割れています