提高 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

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

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

Answer 2

你可以先从两个方面进行优化： 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;

提高 Sieve 方法的性能

Improving performance on Sieve method

java

queue

sieve