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;

{
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))
{
}
}
}

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))
{
}

}

}

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

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

}
}
}
``````

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