ナイーブ素数テストの最適化

Question

私はhttp://en.wikipedia.org/wiki/Primality_test#Naive_methods

 static boolean check(int n) 
    { 
      if(n == 2 || n == 3) 
      { 
        return true; 
      } 
      if(n < 2 || n % 2 == 0 || n % 3 == 0) 
      { 
        return false; 
      } 
      for(int i = 6; i * i <= n; i += 6) 
      { 
        if(n % (i - 1) == 0 || n % (i + 1) == 0) 
        { 
          return false; 
        } 
      } 
      return true; 
    } 

ここに記載されているとして、ナイーブな実装を使用して素数をテストするためのアルゴリズム、私は6K + 1セクションにすべての方法を得たが、その後、私は」を持っています失われた。他にどのように私はこの速度をさらに最適化できますか？

Answer 1

あなたは素朴な方法に固執する場合は、あなたの次のステップはにあなたがリンクするウィキペディアのページに記載されている次のプロパティを使用することです。だから、すべての素数は、フォーム30K + Iである

（すなわち、gcd（i、30）= 1となるように）i = 1、7、11、13、17、 19,23,29である。

あなたは、30ステッピングループと6ステッピングループを交換（およびすべてが手作業で30未満をプライムに確認してください）でしょう2.3.5

よりもわずかに異なる/より多くの素数を選ぶかもしれません除き

ですから、これは8/30（= 27％）の数字をスキャンしていることに注意しましょうしかし

static boolean check(int n) 
    { 
      if(n<30) 
      { 
       return n==2 || n==3 || n==5 || n==7 || ... 
      } 

      for(int i = 30; i * i <= n; i += 30) 
      { 
       if (n % (i + 1))==0 return false; 
       if (n % (i + 7))==0 return false; 
       if (n % (i + 11))==0 return false; 
       if (n % (i + 13))==0 return false; 
       if (n % (i + 17))==0 return false; 
       if (n % (i + 19))==0 return false; 
       if (n % (i + 23))==0 return false; 
       if (n % (i + 29))==0 return false; 
      } 
      return true; 
    } 

、6ステッピングループスキャンしばらく2/6 （= 33％）：

コードは次のようになります。それはaboをスキャンするあなたは20％少ない数字しかないので、最高20％のスピードアップを期待できます。リストにさらに素数を追加すると、リターンが小さくなります。

本当に素早いプライムチェックが必要な場合は、素朴な方法から離れる必要があります。以前はスタックオーバーフローに関する質問がたくさんありました。