Generate All Prime Numbers up to N (Sieve of?

Eratosthenes)

List<int> GeneratePrimes(int n)

bool[] isPrime = new bool[n + 1];

for (int i = 2; i <= n; i++) isPrime[i] = true;

for (int i = 2; i * i <= n; i++)

if (isPrime[i])

for (int j = i * i; j <= n; j += i)

isPrime[j] = false;

List<int> primes = new List<int>();

for (int i = 2; i <= n; i++)

if (isPrime[i]) primes.Add(i);

return primes;

Explanation:

Mark multiples of each prime as non-prime starting from its square.

Follow on: