Skip to content

Instantly share code, notes, and snippets.

@sorashi
Last active June 9, 2021 03:22
Show Gist options
  • Save sorashi/8c37210d0a357b933d59f249f2b449e0 to your computer and use it in GitHub Desktop.
Save sorashi/8c37210d0a357b933d59f249f2b449e0 to your computer and use it in GitHub Desktop.
Prime number utilities
public static bool IsPrime(int candidate) {
if ((candidate & 1) == 0)
return candidate == 2;
for (int i = 3; (i * i) <= candidate; i += 2)
if ((candidate % i) == 0)
return false;
return candidate != 1;
}
public static IEnumerable<int> ComputePrimes(int limit)
{
limit++;
var primes = new BitArray(limit, true);
primes.Set(0, false);
primes.Set(1, false);
var lastI = 0;
for (int i = 0; i * i < limit; i++)
{
if (primes.Get(i))
{
yield return i;
for (int j = i * i; j < limit; j += i)
{
primes.Set(j, false);
}
}
lastI = i;
}
for(var i = lastI + 1; i < limit; i++){
if(primes.Get(i)) yield return i;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment