问题描述
我已经写了一个算法，我认为是正确的计算素数最多n个与埃拉托色尼的筛。不幸的是，这个程序挂在n个真正的大值（试行10元）。以下是我已经写了...
I've written an algorithm that I believe to be correct for computing prime numbers up to n with the Sieve of Eratosthenes. Unfortunately, this program hangs on really large values of n (try 10 million). Here is what I've written...
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
我怎么可能会加速这一算法呢？哪里是我的瓶颈？
How might I speed this algorithm up? Where are my bottlenecks?
推荐答案
从大名单中删除元素是缓慢的。
Removing elements from a large list is slow.
为什么不创建布尔值的数组来代替，而设置一个值设置为真，当你知道它的非黄金？
Why not create an array of Booleans values instead and set a value to "True" when you know that it's non-prime?
当你发现了一个新总理，你不需要去通过的所有的较高值，即一个刚刚多个，数组元素设置为True。
When you've found a new prime, you don't need to go through all higher values, just multiple of that one, setting the array element to True.
您可以保留为素数的单独列表你发现，到目前为止，如果你要回报他们。
You can keep a separate list for primes you've found so far, if you want to return them.
下面是一个C＃实现，它只是打印出来，因为它去。 （在C＃中，如果我想返回我返回的IEnumerable和LT的值; T＆GT; 和使用迭代器块）
Here's a C# implementation which just prints them out as it goes. (In C# if I wanted to return the values I'd return IEnumerable<T> and use an iterator block.)
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);
}
}
}
这篇关于帮助加快这一算法？埃拉托色尼筛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！