Необходимо увеличить скорость поиска больших простых чисел через сито Эратосфена

Question

Данные код имеет оптимизацию по памяти. Так это сито сегментированное. Мне нужна оптимизация по времени.

WinForm

        void simpleSieve(ulong limit, ArrayList prime)
        {

            bool[] mark = new bool[limit + 1];

            for (int i = 0; i < mark.Length; i++)
                mark[i] = true;

            for (ulong p = 2; p * p < limit; p++)

            {

                if (mark[p] == true)
                {

                    for (ulong i = (ulong)(p * p); i < limit; i += (ulong)p)
                        mark[i] = false;
                }
            }


            for (ulong p = 2; p < limit; p++)

            {
                if (mark[p] == true)
                {
                    prime.Add(p);
                    richTextBox1.AppendText(p + " ");

                }
            }
        }

        void segmentedSieve(ulong n)
        {

            int limit = (int)(Math.Floor(Math.Sqrt(n)) + 1);
            ArrayList prime = new ArrayList();
            simpleSieve((ulong)limit, prime);


            ulong low = (ulong)limit;
            ulong high = (ulong)(2 * limit);


            while (low < n)
            {
                if (high >= n)
                    high = n;


                bool[] mark = new bool[limit + 1];

                for (int i = 0; i < mark.Length; i++)
                    mark[i] = true;


                for (int i = 0; i < prime.Count; i++)
                {

                    ulong loLim = ((ulong)Math.Floor((double)(low / (ulong)prime[i])) * (ulong)prime[i]);
                    if (loLim < low)
                        loLim += (ulong)prime[i];


                    for (ulong j = loLim; j < high; j += (ulong)prime[i])
                        mark[j - low] = false;
                }


                for (ulong i = low; i < high; i++)
                    if (mark[i - low] == true)
                        richTextBox1.AppendText(i + " ");
                low = low + (ulong)limit;
                high = high + (ulong)limit;
            }
        }

Console

 static void simpleSieve(int limit,
                        ArrayList prime)
{
    /
    bool[] mark = new bool[limit + 1];
     
    for (int i = 0; i < mark.Length; i++)
        mark[i] = true;
 
    for (int p = 2; p * p < limit; p++)
    {
       
        if (mark[p] == true)
        {
            
            for (int i = p * p; i < limit; i += p)
                mark[i] = false;
        }
    }
 
   
    for (int p = 2; p < limit; p++)
    {
        if (mark[p] == true)
        {
            prime.Add(p);
            Console.Write(p + " ");
        }
    }
}
 

static void segmentedSieve(int n)
{
    
    int limit = (int) (Math.Floor(Math.Sqrt(n)) + 1);
    ArrayList prime = new ArrayList();
    simpleSieve(limit, prime);
 
    
    int low = limit;
    int high = 2*limit;
 
    
    while (low < n)
    {
        if (high >= n)
            high = n;

        
        bool[] mark = new bool[limit + 1];
         
        for (int i = 0; i < mark.Length; i++)
            mark[i] = true;
 
        
        // primes in current range
        for (int i = 0; i < prime.Count; i++)
        {
            
            int loLim = ((int)Math.Floor((double)(low /
                        (int)prime[i])) * (int)prime[i]);
            if (loLim < low)
                loLim += (int)prime[i];
 
            
            for (int j = loLim; j < high; j += (int)prime[i])
                mark[j-low] = false;
        }
 
        
        for (int i = low; i < high; i++)
            if (mark[i - low] == true)
                Console.Write(i + " ");
 
        
        low = low + limit;
        high = high + limit;
    }
}
 

static void Main()
{
    int n = 100;
    Console.WriteLine("Primes smaller than " + n + ":");
    segmentedSieve(n);
}

Answer 1

Понизить асимптотическую сложность данного алгоритма без ущерба потреблению памяти практически невозможно.

Но здесь можно сделать следующие вещи:

Уменьшить количество генерируемого мусора, это позволит сборщику реже останавливтаь код для сборки, следовательно увеличит производительность кода.
Данные, используемые часто разместить в массиве, а не в списке для блоее быстрого к ним доступа.
Избавиться от вывода на экран во время расчетов, результатом работы метода считать наполненную коллекцию простых чисел, смысл выводить на экран 50847534 чисел, верно? Вы же никогда не сможете визуально проверить каждое.
Избавиться от лишних приведений типов, если это не повлияет на результат работы. long.MaxValue - вполне достаточно для задания интервала поиска. Если вы зададите это число, считать будет очень долго, поэтому увеличение его в 2 раза за счет ulong не считаю полезным.

static void Main(string[] args)
{
    Stopwatch sw = Stopwatch.StartNew();
    List<long> result = SegmentedSieve(1000000000);
    Console.WriteLine($"Elapsed = {sw.Elapsed}");
    Console.WriteLine($"Total numbers = {result.Count}");
    Console.ReadKey();
}

static void SimpleSieve(int limit, List<long> prime)
{
    bool[] mark = new bool[limit];

    for (int p = 2; p * p < limit; p++)
    {
        if (!mark[p])
        {
            for (int i = p * p; i < limit; i += p)
                mark[i] = true;
        }
    }

    for (int p = 2; p < limit; p++)
    {
        if (!mark[p])
            prime.Add(p);
    }
}

static List<long> SegmentedSieve(long n)
{
    int limit = (int)Math.Ceiling(Math.Sqrt(n));
    List<long> result = new(limit);
    SimpleSieve(limit, result);
    long[] prime = result.ToArray();

    long low = limit;
    long high = 2 * limit;
    bool[] mark = new bool[limit];

    while (low < n)
    {
        if (high >= n)
            high = n;

        foreach (long p in prime)
        {
            long loLim = low / p * p;
            if (loLim < low)
                loLim += p;

            for (long j = loLim; j < high; j += p)
                mark[j - low] = true;
        }

        for (long i = low; i < high; i++)
            if (!mark[i - low])
                result.Add(i);

        low += limit;
        high += limit;
        Array.Fill(mark, false);
    }

    return result;
}

Вывод в консоль Debug сборки

Elapsed = 00:00:08.8822729
Total numbers = 50847534

Вывод в консоль Release сборки

Elapsed = 00:00:03.3784039
Total numbers = 50847534

3,4 секунды - думаю, неплохо

БЛОГ НА HUSL

Необходимо увеличить скорость поиска больших простых чисел через сито Эратосфена

Ответы (1 шт):