改进筛法的性能

Question

我正在编写一种方法来查找高达n的素数（埃拉托色尼筛），是的，这是为了家庭作业。我希望在我编写的方法中提高性能。在过去的几天里，我一直在调整这个，但无法遵循给定的伪代码并提高性能。

伪代码如下：
创建一个数字队列来处理
用包含2到n的整数填充队列
创建一个空的结果队列来存储素数
重复以下步骤：
通过从数字队列中删除第一个值来获取下一个素数p
将p放入素数的结果队列
循环通过数字队列消除所有可被p整除的数字
同时（p小于n的平方根）
所有剩余值都是素数，因此将它们转移到素数结果队列

这是我目前的方法：

 public static Queue<Integer> getPrimes(int n) throws IllegalArgumentException
{
    if (n<2)
    {
        throw new IllegalArgumentException();
    }

    Queue<Integer> integers = new LinkedList<Integer>();
    Queue<Integer> primes = new LinkedList<Integer>();
    for (int i = 2; i <= n ; i++) {
        integers.add(i);
    }
    boolean[] isMultiple = new boolean[n + 1];

    for(int iterate = integers.remove(); iterate <= n; iterate++)
    {

        if(!isMultiple[iterate])
        {
            primes.add(iterate);
            for(int multiples = iterate * iterate; multiples >= 0 && multiples <= n; multiples += iterate)
            {
                isMultiple[multiples] = true;
            }
        }
    }
    return primes;
}

Answer 1

作为第一个小步骤，您可以删除整数队列并将其替换为常见的for循环：

for (int iterate = 2; iterate < n; iterate++)
{
     if (!isMultiple[iterate]) 
     {
         ...
     }
}

Answer 2

首先可以用两种方法优化它：1）不需要整数linkedlist。而是使用一个简单的for循环。

2）使用for循环后，您可以首先删除所有偶数，因为它们显然可以被2整除。然后遍历奇数。从而将循环减半。

代码段：

    primes.add(2);
    for(int i=2;i*i<=n;i++)
    {
        isMultiple[2*i]=true;
    }
    for(int i=3;i*i<=n;i+=2)
    {
        if(!isMultiple[i]) 
        {
            primes.add(i);
            for(int j=i*i;j<n;j+=i)
            {
               isMultiple[j]=true;
            }
        }
    }
    return primes;