这个程序使用埃拉托斯特尼的筛子吗？

Question

我的任务如下：使用埃拉托斯特尼筛来定位并打印出从1到1000的所有素数。

遵循与此类似的过程:

< li >按顺序写下所有需要考虑的数字。 < li >划掉1，因为它不是质数。 < li >转到未删除的下一个号码；留下它，但是划掉那个数字的所有倍数。 < li >重复步骤3，直到您超过所考虑的最大值的一半。在这一点上，所有没有被划掉的数字都是期望的素数。

您的算法可能与上述算法略有不同，但速度很重要。

我用我所掌握的数学和数组知识编写了这个程序，但当我在研究Sieve时，我不知道这是否是一种方法。

public class PrimeSieve
 {

     public static void main( String[] args) 
     { 
         int max=1000;
         calcPrimes( max ); 
        } 

        public static void calcPrimes( int max ) 
        { 
            // each boolean value indicates whether corresponding index 
            // position is composite (non-prime) 
            boolean[] array = new boolean[max +1 ]; 

            // mark composites as true 
             for (int i = 2; i <= (int) Math.sqrt( max ); i++) 
             {
                 for (int j = i*i; j <= max; j += i) array [j ] = true; 
                 {

             // print indexes with corresponding false values 
                    for (int k = 2;k <= max; k++) 
                    {

                        if ( !array[ k ] ) 
                        System.out.format( k + "\n" ); 
                    }

                }
            }
      } 
} 

任何帮助都很好！

Answer 1

问题是，在打印结果之前，您没有完成划分组合的过程，这可能是因为您的循环以一种混乱的方式嵌套。

public static void calcPrimes(int max) {
    // each boolean value indicates whether corresponding index
    // position is composite (non-prime)
    boolean[] array = new boolean[max + 1];

    // mark composites as true
    for (int i = 2; i <= (int) Math.sqrt(max); i++) {
        for (int j = i*i; j <= max; j += i) array[j] = true;
    }

    // print indexes with corresponding false values
    for (int k = 2; k <= max; k++) {
        if (!array[k]) System.out.println(k);
    }
}

在这个例子中，我移动了代码来打印执行筛选的循环之外的素数。