エラトステネスのふるいは、すべての数字が素数であると考えている127

Question

私の篩のエラトステネスに問題があります。私は、あなたが望む最大の素数まですべての数字の配列を必要とせず、代わりにSieveがそれに達するごとに各素数を追跡するSieveを書こうと思っていました。つまり、すべての作業を前もってやる必要はなく、必要なときに次の素数を決定するだけです。また、「Nから始まるK個の素数を見つける」のようなインターフェイス機能を追加することも簡単です。ここで擬似コードは次のとおりです。

Begin with current number set to 2 
Loop: 
    If prime queue is not empty: 
     Peek at the top prime in the queue 
     If current > top, we can move top to the next multiple 
      Remove the top prime from the prime queue 
      Increment top to its next multiple 
      Re-add it to the queue 
     If current == top, current is not a prime 
      Increment current number to next integer 
     If current < top, we've found a prime 
      Break 
Push current number onto prime queue 
Increment current number to next integer 
Return the new prime 

ので、ここで問題です：私は正常に（127まで）最初の31個の素数を計算し、それの後にそれがすべての数が素数であると考えています。私はIdeoneに自分のコードを書いています - アルゴリズム自体ではなく、Javaのコレクションの動作、または簡単なバグだと思っています。特定の数の素数の後にアルゴリズムが壊れなければならない理由は考えられません。私は手動で、127の後に、ヒープが適切に順序付けされていると、私のアルゴリズムは128をプライムではないと認識するはずですが、それはコードが私に示すものではありません。

提案がありますか？

http://ideone.com/E07Te

（Iは、2によるもちろん、増分（私は基本的なアルゴリズムが働いて得れば。私はおそらくもふるい反復可能な作ります）すべての非プライム偶数をスキップします。）

Answer 1

あなたの問題は、私が正しくリコール場合は絶対値が小さいInteger秒、127へ-128のキャッシュは、あり

Integer current = 2; 
Integer multiple; 

に関連して

top.multiple == current 

なので、比較は==を使用して同じインスタンスを128より小さい値で比較します。しかし、128からはの新しいボックスcurrentが得られます。これはoとは異なるオブジェクトですneはtop.multipleによって参照される。

equalsを使用して比較するか、int current;を使用して解決してください。

アルゴリズムを改善し、各素数の倍数は素数の正方形からのみ注意してください。

Answer 2

あなたはあなたの全体のリストをチェックしていない：、あなたが132に到達する128]

た： [[127：127]、[11：132]、[2 31後

ふるいヒープ> 128であり、従ってyoの前にbreak;を打つ2 * 64をチェックしてください。