java - 提高 Sieve 方法的性能

Question

我正在编写一种方法来查找不超过 n(埃拉托色尼筛法)的素数，是的，这是作业。我希望提高我编写的方法的性能。最近几天我一直在调整它，但无法遵循给出的伪代码并提高性能。

伪代码如下:
创建要处理的号码队列
用从 2 到 n 的整数填充队列
创建一个空的结果队列来存储素数
重复以下步骤:
通过从数字队列中删除第一个值来获得下一个素数 p
将p放入素数结果队列
遍历数字队列，消除所有可被 p
整除的数字while(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

首先可以通过两种方式进行优化:1) 你不需要 integer 链表。而是使用简单的 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;