帮助加速此算法？Eratosthenes筛子

Question

我已经写了一个算法，我相信这个算法是正确的，可以用Eratosthenes的筛子来计算直到n的质数。不幸的是，这个程序挂起了非常大的n值(尝试1000万)。这是我写的..。

Protected Function Eratosthenes(ByVal n As Integer) As String
    Dim maxValue As Integer = Math.Sqrt(n)
    Dim values As Generic.List(Of Integer) = New Generic.List(Of Integer)
    Dim i As Integer
    ''//create list.
    For i = 2 To n
        values.Add(i)
    Next

    For i = 2 To maxValue
        If values.Contains(i) Then
            Dim k As Integer
            For k = i + 1 To n
                If values.Contains(k) Then
                    If (k Mod i) = 0 Then
                        values.Remove(k)
                    End If
                End If
            Next
        End If
    Next

    Dim result As String = ""
    For i = 0 To values.Count - 1
        result = result & " " & values(i)
    Next

    Return result
End Function

我如何才能加速这个算法呢？我的瓶颈在哪里？

Answer 1

从大型列表中删除元素的速度很慢。

为什么不创建一个布尔值的数组，并将一个值设置为"True“，当您知道它是非质数时？

找到新的素数时，不需要遍历所有更高的值，只需将数组元素设置为True即可。

如果你想返回素数，你可以为你已经找到的素数保留一个单独的列表。

这是一个C#实现，它可以在运行过程中将它们打印出来。(在C#中，如果我想返回值，我将返回IEnumerable<T>并使用迭代器块。)

using System;

public class ShowPrimes
{
    static void Main(string[] args)
    {
        ShowPrimes(10000000);
    }

    static void ShowPrimes(int max)
    {        
        bool[] composite = new bool[max+1];
        int maxFactor = (int) Math.Sqrt(max);

        for (int i=2; i <= maxFactor; i++)
        {
            if (composite[i])
            {
                continue;
            }
            Console.WriteLine("Found {0}", i);
            // This is probably as quick as only
            // multiplying by primes.
            for (int multiples = i * i;
                 multiples <= max;
                 multiples += i)
            {
                composite[multiples] = true;
            }
        }
        // Anything left is a prime, but not
        // worth sieving
        for (int i = maxFactor + 1; i <= max; i++)
        {
            if (composite[i])
            {
                continue;
            }
            Console.WriteLine("Found {0}", i);
        }
    }
}

Answer 2

我不是一个VB的人，但我认为：

values.Remove(k)

是浪费时间的，只需将位置设置为0，然后将质数提取到另一个列表中，或者对相同的列表进行排序并一次性删除所有零。

Answer 3

你的瓶颈是使用列表，简单明了。List.contains为O(n)，List.Remove(n)。

您将通过使用更好的数据结构(即BitArray )来加速您的应用程序。假设设置为True的项目是质数，而不是合成的项目。这意味着在素数集中查找、添加或删除项将是O(1)操作。