昨日アップした素数を求めるプログラム。
いろいろと考えてさらにスピードアップに成功しました。
sosuu()関数を次のものと差し換えればＯＫです。
ちょっと強引なところもありますが、自然数の性質から導ける理論を使った
純粋にアルゴリズムによる高速化です。

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
sosuu()
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
int sosuu(int n)
/* nまでの素数を求める */
/* 素数とは１とそれ自身でしか割り切れない数 */
/* １は素数ではない（定義） */
{
int nn,s,ss;
        if (n<=3) { /* ３以下の時はすべて素数 */
                for (s=2;s<=n;s++) printf(",%d",s);
                return(n-1);
        }
        /* ４以上の時 */
        printf("2,3");
        nn=2; /* 個数は2,3の2個からスタート */
        /* しかし４は素数でないのでいきなり省く */
        for (s=5;s<=n;s++) {
                /* ２か３で割り切れる時は素数でない */
                if ((s%2)==0 || (s%3)==0) continue;
                /* その数が割切れる数はそれ自身以外はそれ自身／２未満である */
                /* さらに３で割り切れない時はそれ自身／３未満である */
                /* また、４は２で割り切れるからさらにそれ自身／４未満である */
                for (ss=5;ss<s/4 && (s%ss)!=0;ss++);
                if (ss>=s/4) {
                        printf(",%d",s);
                        nn++;
                }
        }       printf("￥n");
        return(nn);
}
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

説明はプログラム中にコメントで入れてありますから特にしませんが、
要するに絶対に割り切れない数による判定を省いたということです。
これでもまだ甘いと思います・もっと考えればもっと割ってみる数が減るでしょう。
そうすればもっと高速化が可能と思います。

速度の違いは次の如く劇的に変ります。

１００００まで１２３０個の素数を求める
        Ｘ６８０００　１２ＭＨｚの場合
                旧型    ２：３７
                新型    ０：４８

実に３．３倍ものスピードアップがなされています。
そもそもコンピューターにとって剰余演算というものは得意なものではないですから、
できるだけその数を減らしてやれば確実にスピードアップします。
例えば５まで別判定して、ss<s/5にしてやればさらにスピードアップするのは
わかるでしょう。そうなると６も割り切れるからss<s/6迄も行けるようになるので
もっともっとスピードアップするでしょう。そうすればＸ６８０００でも
旧型アルゴリズム＋３８６／２０ＭＨｚの速さ以上にまですることが可能でしょう。

ああ、アルゴリズムって不思議。

・・・2003/04/02修正
１は素数ではないと指摘を受けましたので修正しました。