Alexander Ameye Alexander Ameye -3 years ago 250
C# Question

C# Sieve of Eratosthenes

I have written this code to find prime numbers, and it works well, but the calculation speeds are incredibly slow..... Am I doing this wrong? I know that I might be really doing this the wrong way, but please help me! Thank you very much!

using System;
using System.Collections.Generic;

namespace Primenumbers
{
class MainClass
{
public static void Main (string[] args)
{
List<int> NoPrime = new List<int>();

for(int x = 2; x < 10000;x++)
{
for(int y = x * 2;y < 10000;y = y + x)
{
if(!NoPrime.Contains(y))
{
NoPrime.Add(y);
}
}
}

for(int z = 2; z < 10000;z++)
{
if(!NoPrime.Contains(z))
{
Console.WriteLine(z);
}
}
}
}
}


EDIT:
This is the new code, I changed 'List' to 'HashSet' and added a counter to get the sum of all the prime numbers. A big thank you to everyone who commented/answered, you guys are awesome!

using System;
using System.Collections.Generic;

namespace Problem7
{
class MainClass
{
public static void Main (string[] args)
{


HashSet<int> NoPrime = new HashSet<int>();

long count = 0;
int n = 2000000;

for(int x = 2; x < n;x++)
{
for(int y = x * 2;y < n;y = y + x)
{

if(!NoPrime.Contains(y))
{
NoPrime.Add(y);
}

}

}

for(int z = 2; z < n;z++)
{
if(!NoPrime.Contains(z))
{
Console.WriteLine(z);
count = count + z;
}
}

Console.WriteLine("Sum is: " + count);


}
}
}

Answer Source

Complexity of your code is between O(n * (n log n)) and O(n ^ 3) (not exactly sure) instead of O(n log log n) (see Sieve of Eratosthenes: Complexity ). The higher complexity caused by

  • linear search in NoPrime list (give an extra n to complexity)
  • lack of "find next prime" check in outer loop - so inner loop have complexity of more than O(log log n)

To fix:

Change to Dictionary<int,bool> (or better yet to HashSet<int> as suggested in comments) to get O(1) complexity for Contains. Alternatively you can implement algorithm directly by per-allocating large array of bool for each number and mark items true (again giving O(1) check if number is prime or not).

Add check in outer loop to skip inner iteration where x is not prime.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download