使埃拉托斯特尼筛更有效

Question

在一个类作业中，我被要求用Java编写Eratostenes筛选代码，我的代码效率非常低。运行时间不长，但我相当肯定，除了像我一样列出所有内容外，还有其他循环的空间。。

这是我的代码:

public class test
{

    public static boolean[] myArray()
    {
        boolean[] myArray = new boolean[100];
        for(int i = 1;i <100; i++)
        {
                if(i % 2 ==0)
                    {
                        myArray[i] = true;
                    }
                if(i % 3 ==0)
                    {
                        myArray[i]= true;
                    }
                if(i % 5 ==0)
                {
                    myArray[i]= true;
                }
            if(i % 7 ==0)
                {
                    myArray[i]= true;
                }
            if(i % 11 ==0)
                {
                    myArray[i]= true;
                }
        }
        myArray[2]=false;
        myArray[3]=false;
        myArray[5]=false;
        myArray[7]=false;
        myArray[11]=false;

        return myArray;
    }       
}

基本上，我所做的是将所有不是质数的元素设置为true…

所以我的主要2个问题是1。有没有办法实现一个循环，使代码更短2。如何打印此数组中所有为 true（质数）的元素

Answer 1

你在这里做的是将2、3、5、7和11的所有倍数标记为true，然后将这些数字本身设置为false，但你要做100次。

您需要为筛子做以下工作:

最初，所有的数字都是“质数”，直到被标为合数。

< li >将数组中的所有数字标记为< code>true，即“迄今为素数”。 < li >在< code>for循环中，如果该数字仍然< code>true，则它是质数。从该数字的两倍开始，将它的所有倍数标记为< code>false表示合成。您可以为此使用一个内部循环。 < li >否则，如果该数字为< code>false，则它是复合的，并且它的倍数也已经标记为复合的。 < li >迭代完< code>100、< code>10的平方根后，停止< code>for循环。这种优化是可能的，因为您不会找到更多的数字来标记composite。如果此处的数字是复合数字，并且是大于< code>10的倍数，那么还有一个小于< code>10的因子已经将该数字标记为复合数字。

Answer 2

我希望这有帮助。无论如何，筛子是一个很长的话题：

public class test
{

    public static boolean[] myArray(int MAX)
    {
        boolean[] myArray = new boolean[MAX+1];
        // myArray[i] == false iff i is prime
        for(int i = 2; i*i <= MAX; i++) // optimization: i*i to not check repeated divisors
        {
            if (!myArray[i]) // if i is prime
                for (int j=i+i; j <= MAX; j += i) // mark all its multiples as not prime
                    myArray[j] = true;
        }
        return myArray;
    }    

    public static void print(int[] myArray) { // print the array once computed
        for (int i=2; i< myArray.length; ++i)
            if (!myArray[i])
                System.out.println(i+" is prime");
    }   
}

附注:代码未经测试。