vb.net – 帮助加快这个算法？ Eratosthenes的筛子

发布时间：2020-12-17 07:26:36 所属栏目：百科来源：网络整理

导读：我已经编写了一个算法,我认为使用Eratosthenes的Sieve来计算高达n的素数是正确的.不幸的是,这个程序依赖于非常大的n值(尝试1000万).这是我写的…… Protected Function Eratosthenes(ByVal n As Integer) As String Dim maxValue As Integer = Math.Sqrt(n)

我已经编写了一个算法,我认为使用Eratosthenes的Sieve来计算高达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”？

当你找到一个新的素数时,你不需要经历所有更高的值,只需要多个值,将数组元素设置为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);
        }
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!