エラトステネスの篩は素数を篩い分けしません

Question

私の授業の1つでは、私たちはエラトステネス篩を実装する必要があります。私は7回試みて、働いているコードを得て、私が研究した多数のソリューションを組み込んだ。私は最終的に数字を出力するものを持っています。残念ながら、それは両方の複合と素数を印刷し、次のように2

私のコードは印刷されません。

public class EratosthenesSieveAttempt6 { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 
     Scanner keyboard = new Scanner(System.in); 
     int limit; 

     System.out.print("Please enter the highest number to check " 
       + "(number must be greater than 2): "); 

     limit = keyboard.nextInt(); 

     while (limit <= 2){ 
      System.out.println("Error - number must be greater than 2."); 
      System.out.println("Please enter the highest number to check: "); 
      limit = keyboard.nextInt(); 
     } 

     boolean[] numbers = new boolean[limit + 1]; 
     int newPrime = 2; 

     for(int i = 0; i < limit + 1; i++){ 
      numbers[i] = true;  
     } 

     for(int j = 1; j < limit + 1; j++) { 
      if (j % 2 == 0) { 
      numbers[j] = false; 
      } 

     for(int k = j + 1; k < limit + 1; k++) { 
      if(numbers[k] == true){ 
      j = k; 

     System.out.println(k); 
       } 
      } 
     } 
     } 
    } 

私は私のループに問題があることを疑っています。最初の2つのループのためにiとjの変数を修正しました。これは、2以降から出力されるようになりました。問題は、配列をtrueに初期化した後にfalseと表示しているようです。

ご協力いただきありがとうございます。

Answer 1

ここに私が先日書いたエラトステネスのふるいの実装です：

import java.util.BitSet; 

public static BitSet composite(int max) { 
    BitSet composite = new BitSet(max); 
    max = composite.size(); 
    for (int i = 4; i < max; i += 2) composite.set(i, true); 
    for (int i = 9; i < max; i += 6) composite.set(i, true); 
    int p = 5; 
    while (p*p < max) { 
     if (!composite.get(p)) { 
      for (int i = p*p; i < max; i += p*2) composite.set(i, true); 
     } 
     p += 2; 
     if (p*p >= max) break; 
     if (!composite.get(p)) { 
      for (int i = p*p; i < max; i += p*2) composite.set(i, true); 
     } 
     p += 4; 
    } 
    return composite; 
} 

注：

• たBitSetは、64ビット・ワードを割り当て、そのサイズは（あなたが要求したより大きくてもよいです例えば、1000まで上がるように頼むと1024まで上がると、それは上に近いmax = composite.size()の理由です）
• 2と3を明示的に取得してから
• 3より大きいすべての素数が1または5 mod 6のいずれかに一致するという事実に依拠します。これは、最終ループが2と4を交互に繰り返す理由です。

これは、複合番号であることを示すBitSetを返します。それからわずか素数を抽出する1つの方法は次のようになります。

public static int[] primes(BitSet composite) { 
    int size = composite.size() - 2 - composite.cardinality(); 
    int[] primes = new int[size]; 
    int index = 0; 
    for (int i = 2; i < composite.size(); i++) { 
     if (!composite.get(i)) primes[index++] = i; 
    } 
    return primes; 
}