1

我正在编写一种方法来找到 n（Eratosthenes 筛）的素数，是的，这是为了家庭作业。我希望在我编写的方法中提高性能。过去几天我一直在调整它，但无法遵循给出的伪代码并提高性能。

伪代码如下：
创建一个数字队列来处理
用整数 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;
}
4

2 回答 2

3

您可以首先通过两种方式对其进行优化：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;
于 2015-02-25T19:27:24.427 回答
0

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

for (int iterate = 2; iterate < n; iterate++)
{
     if (!isMultiple[iterate]) 
     {
         ...
     }
}
于 2015-02-25T19:13:08.520 回答