CODEWITHSUNDEEP
c#primessieve-of-eratosthenessieve-algorithm
Gustav Blomqvist
Gustav Blomqvist

Reputation: 161

Sieve of Eratosthenes Optimization

I've made my own program that finds primes from 2 - n, using the Sieve of Eratosthenes. Is there any way I can implement a more efficient way to remove composite numbers?

Link to project: https://github.com/Gurran/Sieve-of-Eratosthenes

class Program
{
    static void Main()
    {
        int max;

        Console.Write("Enter max number: ");
        max = int.Parse(Console.ReadLine());
        FindPrimes(max);
        Console.ReadLine();
    }

    // Prints numbers.
    public static void PrintMap(List<int> List)
    {
        for (int i = 0; i < List.Count; i++)
        {
            if (i % 10 == 0)
                Console.WriteLine();
            Console.Write(List.ElementAt(i) + ", ");
        }
    }

    // Generates list containing 2 - max
    // Removes non-primes
    // Calls PrintMap method
    public static void FindPrimes(int max)
    {
        int x = 2;
        List<int> NrRange = new List<int>();

        for (int i = 2; i < max; i++)
            NrRange.Add(i);
        for (int i = 0; i < NrRange.Count; i++)

            for (int j = x; j < NrRange.Count; j++)
                if (NrRange.ElementAt(j) % x == 0)
                    NrRange.RemoveAt(j);
            x++;
        PrintMap(NrRange);
    }
}

Upvotes: 1

Views: 1558

Answers (3)

yuanbing
yuanbing

Reputation: 11

my code: https://github.com/ktprime/ktprime/blob/master/PrimeNumber.cpp benchmark as fllows:

                          i3-350M,i5-3470,i7-7500u,i7-6700,r7-1700
Pi(0,    1e10) = 455052511    3.10   1.84    1.55     1.32    1.65
Pi(1e11, 1e10) = 394050419    4.35   2.50    2.02     1.78    2.00
Pi(1e12, 1e10) = 361840208    5.30   3.00    2.40     2.04    2.25
Pi(1e13, 1e10) = 334067230    6.52   3.50    2.85     2.39    2.67
Pi(1e14, 1e10) = 310208140    7.90   4.20    3.50     2.87    3.20
Pi(1e15, 1e10) = 289531946    9.90   5.10    4.32     3.49    3.91
Pi(1e16, 1e10) = 271425366    11.7   6.10    5.11     4.12    4.73
Pi(1e17, 1e10) = 255481287    13.9   7.09    5.95     4.84    5.63
Pi(1e18, 1e10) = 241272176    17.2   8.58    7.17     5.82    6.88
Pi(1e19, 1e10) = 228568014    24.0   11.6    9.86     8.00    9.50
Pi(0-1e9,10^9) = 22537866     8.15   4.28    3.92     3.02    3.64
Pi(1e18, 10^6) = 24280        0.65   0.46    0.34     0.48    0.60
Pi(1e18, 10^8) = 2414886      1.30   0.81    0.70     0.60    0.70
Pi(1e18, 10^9) = 24217085     3.50   1.80    1.58     1.26    1.50
Pi(0,    1e12) = 37607912018  500    270     224      200     220
Pi(1e14, 1e12) = 31016203073  790    420     354      295     320
Pi(1e16, 1e12) = 27143405794  1160   600     512      420     485
Pi(1e18, 1e12) = 24127637783  1500   760     622      520     640
Pi(1e19, 1e12) = 22857444126  1700   830     702      600     665

Upvotes: 0

GordonBGood
GordonBGood

Reputation: 3517

There are many optimizations to the basic Sieve of Eratosthenes you can make in C#, which becomes important for larger ranges such as billions to trillions, including the techniques of segmentation to reduce memory use and increase cache locality, multiprocessing, wheel factorization to reduce number of composite number culls, and sieving patterns of composites to reduce culling loop complexity, many of which I cover in my answer at: How do I implement the Sieve Of Eratosthenes using multithreaded C#?. These techniques reduce the number of calls per composite number to much less than the ratio of the ideal of one per composite (about a quarter of the range to Sieve to a billion) due to elimination of composites on the wheel factors, and the time is split evenly between the number of cores used.

There is an alternate means of filtering composites by an alternate pattern that speeds that up by about a factor of two, but I've not published that yet. It is faster due to reduced complexity without table lookups of the innermost culling loop(s).

Using another language such as C/C++, Rust, Nim, Haskell, etc. that produces more efficient machine code and allows major unrolling of the composite number culling loop(s) in addition to all of the other techniques is faster yet again, as it can reduce the time required per composite number culling to just above one clock cycle from about 10 clock cycles on a modern desktop CPU. Thus, the time required to cull the composite numbers to a range of a billion can be reduced to about 63 milliseconds on a 3.5 GHz/4 core CPU such as the Intel i7-2700 I used. If you want more than a count of the number of primed, the time will be increased of course.

The techniques used are similar to Kim Walich's open sourced C++ primesieve (https://primesieve.org) except for the new pattern which will make it just slightly faster due to increased wheel factorization and slightly less complexity, but you may find his source code difficult to read and understand (you may find my code difficult to understand as to the wheel factorization patterns unless you are somewhat of a mathematician). However, you should be able to run his program to see what is possible.

As pointed out, your program is not a true Sieve of Eratosthenes but rather an inefficient version of Trial by Division (when corrected). As you will likely not appreciate the complexity of my other solutions (walk before you can run), please have a look at the last of the C# unbounded sieves at:. rosettacode.org/Sieve_of_Eratosthenes#Unbounded, which is somewhat functionally the same as your code but uses the segmented Sieve of Eratosthenes with bit packing (one bit per odd trial number) using odds only numbers as 2 is the only even prime.

Any of the programs to which I have linked will be many many times faster than your program even when fixed other than perhaps for very small ranges.

Upvotes: 1

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

I've run your routine FindPrimes(100) and I've got wrong outcome:

2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, .. 95, 97, 99

Let's write it in some different way:

// If we put "FindPrimes", let's return them: List<int> instead of void
public static List<int> FindPrimes(int max) {
  if (max < 2)
    return new List<int>();

  // Try avoid explict adding .Add(), but generating
  List<int> result = Enumerable
    .Range(2, max - 1)
    .ToList();

  // sieving composite numbers out the initial list
  for (int i = 1; i < result.Count; ++i) {
    int prime = result[i - 1];

    // removing all numbers that can be divided by prime found
    // when removing we should loop backward
    for (int j = result.Count - 1; j > i; --j)
      if (result[j] % prime == 0)
        result.RemoveAt(j); 
  }

  return result;
}

Test

 Console.Write(String.Join(", ", FindPrimes(100)));

Outcome:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ..., 83, 89, 97

Upvotes: 1

Related Questions