我编写了一个算法,我相信该算法对于使用埃拉托斯特尼筛法计算 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
我怎样才能加快这个算法的速度?我的瓶颈在哪里?
从大列表中删除元素的速度很慢。
当您知道它不是素数时,为什么不创建一个布尔值数组并将其设置为“True”呢?
当你找到新的素数时,你就不需要经历all更高的值,只是该值的倍数,将数组元素设置为 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);
}
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)