C# - Sieve of Eratosthenes
IntuitionSieve of Eratosthenes is used to find the prime numbers in O(N) timeCode
# Intuition
Sieve of Eratosthenes is used to find the prime numbers in O(N) time


# Code
```csharp []
public class Solution {
    public IList<IList<int>> FindPrimePairs(int n) {
        List<IList<int>> ans = new();
        if(n < 3)
            return ans;
        HashSet<int> primes = GeneratePrimes(n);

        foreach(var p in primes)
        {
            if(primes.Contains(n - p))
            {
                List<int> cur = new() { p, n-p };
                ans.Add(cur);
                //Remove to avoid duplicate entries. eg, (x,y) and (y,x)
                primes.Remove(p);
                primes.Remove(n-p);
            }
        }

        return ans;

        HashSet<int> GeneratePrimes(int n)
        {
            HashSet<int> res = new();
            bool[] isPrime = new bool[n + 1];
            Array.Fill(isPrime, true);
            isPrime[0] = isPrime[1] = false;

            for(int i = 2; i * i <= n; i++)
            {
                if(isPrime[i])
                {
                    for(int j = i * i; j <= n; j += i)
                        isPrime[j] = false;
                }
            }

            for(int i = 2; i <= n; i++)
            {
                if(isPrime[i])
                    res.Add(i);
            }

            return res;
        }
    }
}
```
['C#']