ちょっとメモ

　
次の枠内ア〜キはある正の整数Ｎについて、素数かどうかを判定するプログラムによる処理を言葉で表したものです。特に支持がない場合には、アから順に処理をします。このとき、次の問いに答えなさい。

＜素数かどうかの判定をする＞
ア　３以上の整数Ｎを打ち込む。
イ　Ａは２とする。
ウ　ＲはＮをＡで割った余りとする。ただし、商は整数の範囲とする。
エ　Ｒが０ならば「素数ではない」と表示し、Ｒが０でなければ、そのまま次へ。
オ　Ａを１増やして、それを新しいＡと決める。
カ　ＡがＮより小さければ、　ウ　へ。ＡがＮと等しければ、そのまま次へ。
キ　「素数である」と表示し、処理を終了する。

　
　
①　このプログラムを実行するとき、アでＮに１３を打ち込むと、オの処理は何回行われますか。この問題は答えだけを書いてください。
　
　
　
②　上の＜素数かどうかの判定をする＞プログラムは、処理の回数が多いので、少なくなるように工夫したいと思っています。そこで、「素数かどうかを判定するには、２からＮで割らなくても、２から√Ｎ（ルートＮ）を超えない最大の整数まで割れば判定できる。」という事実を用いて、ウ〜カの部分を

ａ　Ｂは√Ｎ（ルートＮ）を超えない最大の整数とする。
ｂ　ＴはＮをＡで割った余りとする。ただし、商は整数の範囲とする。
ｃ　Ｔが０ならば「素数ではない」と表示し、Ｔが０でなければ、そのまま次へ。
ｄ　Ａを１増やして、それを新しいＡと決める。
ｅ　ＡがＢより小さければ、ｂへ。ＡがＢと等しければ、そのまま次へ。

とします。Ｎが３７のとき、新しい処理のｄの回数はもとの処理のオの回数より、何回少ないですか。
　
　
途中までで、規則性を見い出す！
　
素数とは、１とそれ自身の数以外の約数が無いもの
(例)１,３,５,７,１１,１３,１７,１９…