Skip to content

Instantly share code, notes, and snippets.

@gpc91
Created June 24, 2022 19:07
Show Gist options
  • Save gpc91/66d35026d60d920a1c171d4081021864 to your computer and use it in GitHub Desktop.
Save gpc91/66d35026d60d920a1c171d4081021864 to your computer and use it in GitHub Desktop.
C# Prime Sieve
/*
* Sieve of Eratosthene, C# implementation by George Corkery (github.com/gpc91)
* Something made for fun, feel free to use without attribution
* For more about the Sieve of Eratosthene, see this wikipedia page: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/
using System;
using System.Collections.Generic;
class Eratosthene
{
// Warning: Don't set this too high, trust me, scary things will happen.
void Sieve(int prime_target = 1000)
{
List<int> numbers = new List<int>();
// populate numbers list (2 -> prime_target).
for (int i = 2; i < prime_target; i++)
{
numbers.Add(i);
}
// The actual sieve: sieve out non-prime numbers leaving only primes behind.
for (int p = 0; p < numbers.Count; p++)
{
for (int n = numbers[p]; n < numbers.Count; n++)
{
if (numbers[n] % numbers[p] == 0)
{
numbers.Remove(numbers[n]);
}
}
}
// print the numbers left in our list. As the numbers list has been sieved the only numbers left should be prime
foreach (int prime in numbers)
{
Console.Write($"{prime}, ");
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment