素数マスターへの道(5)

試し割の効果

最初に書いたプログラムは、あまり速くはありませんでした。理由は、大きな素数が現れた場合に4千回以上も試し割りをしなければならないからです。プログラムを実行した結果、判定する33,333,333個の整数の中に、素数は3,260,532個でありました。全体の約9.8%と、それほど多くはありません。
素数でない数の中で、3の倍数は11,111,106個もあり、これは全体の約33.3%に相当します。結構たくさんありますね。
フェルマーテストやミラー・ラビンテストを行う場合でも、数十回の割り算が必要になります。それなら、小さな素数での試し割は、篩い落とせる量を考えれば、十分役立ちそうです。

どれぐらい篩い落とせるか

今回扱う問題は、奇数しか出てこないので、3,5,7,...と、3から順に試し割をして篩い落とせる値の数を数えてみました。

ある程度大きな素数になると、篩い落とせる値がグッと減りますが、最初の方はかなりの数を落とせることがわかります。

プログラムを改良

ミラー・ラビンテストを行う前に、幾つかの小さい素数で試し割をしておきます。

  for(i=0;i<M;++i)
  {
    if( n%3==0 || n%5==0 || n%7==0 || n%11==0 || n%13==0 || n%17==0 || n%19==0 )printf("0");
    else if( mrtest(2,n) && mrtest(7,n) )printf("1");
    else printf("0");
    n=(n+D)%R;
  }