Skip to content

Instantly share code, notes, and snippets.

@EgorBron
Created February 4, 2023 16:52
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save EgorBron/36632915a379b87eb74cb32abf5d123f to your computer and use it in GitHub Desktop.
Save EgorBron/36632915a379b87eb74cb32abf5d123f to your computer and use it in GitHub Desktop.
Implementation of the "Sieve of Eratosthenes" algorithm for generating prime numbers up to N in C#
/// <summary>
/// Implementation of the "Sieve of Eratosthenes" algorithm for generating prime numbers up to N in C#
/// </summary>
public static class SieveOfEratosthenes {
/// <summary>
/// Checking for a prime number with <see cref="Sieve(int)"/>
/// </summary>
/// <param name="num">Number to check</param>
/// <returns>Is <paramref name="num"/> prime number or not</returns>
public static bool IsPrimeNumber(int num) => Sieve(num).Contains(num);
/// <summary>
/// Generates an array of prime numbers up to <paramref name="generateTo"/>
/// </summary>
/// <param name="generateTo">Array limit</param>
/// <returns>An array of prime integers</returns>
public static int[] Sieve(int generateTo) {
List<int> output = new();
bool[] checks = new bool[++generateTo];
Array.Fill(checks, true);
checks[0] = checks[1] = false;
for (int i = 0; i < checks.Length; i++) {
if (!checks[i]) continue;
for (int j = 2; j <= checks.Length; j++) {
if (i * j >= checks.Length) break;
checks[i * j] = false;
}
}
for (int i = 0; i < checks.Length; i++) if (checks[i]) output.Add(i);
return output.ToArray();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment