第２話 素数を探し出すためには？
では、素数を探索するプログラムを考えてみましょう。
素数であるかどうか、
決めるのはどうしたらよいでしょうか。
例えば、２４１は素数でしょうか。
１から２４１まで順に割っていって、
１と２４１のみでしか割り切れなければ素数です。
この方法だと、２４１が素数であることを確定するために、
２４１回も割り算をしなければなりません。
確かに、コンピュータの性能は驚くほどの能力を持っていますから、
２４１回は一瞬で行ってしまいます。
ですが、４０８１３５９７７等だと流石のコンピュータも苦戦します。
ですから、なるべく計算回数が少なくなるように工夫する必要があります。
１と自分自身は割りきれるに決まっていますから、
１と自分自身はまず除外します。
さらに、２以外の偶数は、すべて素数ではありませんから、
２以外の偶数で割る必要はありません。
ですから、例えば７３なら
２，３，５，７，・・・，７１
とうことになります。
実は、これでもかなり無駄があります。
１８の１と自分自身を除く約数を考えてみて下さい。
２，３，６，９
です。
２で割ったときの商が９です。
さらに、３で割ったときの商が６です。
約数で割った商も約数です。
このことを考慮入れれば、
７３の場合は、
２，３，５，７
で割り切れなければ素数であることが確定します。
最後が７である理由は、７の次の９の場合２乗すると、
９×９＝８１で７３を越えています。
７３が素数であることを確定するには、
ルート７３以下の整数まで割っていけば良いのです。
では、この方針で素数生成プログラムを考えます。
はじめは、１００以下の素数を生成させましょう。
表示は、１０個ごとに表示させるようにして下さい。
条件は、関数f()で1から１００までの整数iを発生させて、
発生させた整数が素数であるかを関数sh(i)で判定させ、
素数の解答がある場合に関数f()において表示させるものとします。
尚、iのルートを求めるにはmath.hをインクルードしておき、
sqrt((double)i)とします。
(double)iとなっているは、sqrtはdouble型でしか入力できないからです。
また、sqrtで出てくる値もdouble型であることに注意しましょう。
皆さん考えてみて下さい。
もちろん、これは最速ではありませんので
話の進行と共にどんどん改良していきます。
