Alexander Ameye -3 years ago 250

C# Question

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);

}

}

}

}

}

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);

}

}

}

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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**

Latest added