Skip to content

Instantly share code, notes, and snippets.

@sonnguyen9800
Created July 12, 2024 10:01
Show Gist options
  • Save sonnguyen9800/66eadb7a607a9ea969b1b4f6dfe6f30e to your computer and use it in GitHub Desktop.
Save sonnguyen9800/66eadb7a607a9ea969b1b4f6dfe6f30e to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes - An algorithm to find prime number
public static class SieveOfEratos {
private static int[] GenerateArray(int n) => Enumerable.Range(2, n-1).ToArray(); // generate from 2 -> n
private static bool[] GenerateArrayOfOnes(int n) => Enumerable.Repeat(true, n).ToArray();
public static int[] SieveofEratosAlgorithm(int upperLimited)
{
int[] allNumbers = GenerateArray(upperLimited);
bool[] allMarker = GenerateArrayOfOnes(allNumbers.Length);
int maxValue = allNumbers[allNumbers.Length - 1]; // last value (always the greatest)
for (int i = 0; i < allNumbers.Length; i++)
{
int currentValue = allNumbers[i];
if (allMarker[i] == false)
continue;
int jumpvalue = currentValue;
for(int value = currentValue + jumpvalue; value <= maxValue; value += jumpvalue)
{
if (value > maxValue)
break;
var index = Array.IndexOf(allNumbers, value);
if (index == -1)
break; //not found
allMarker[index] = false;
}
}
var result = allNumbers.Where((x,i)=>
{
if (allMarker[i] == true)
return true;
return false;
}).ToArray();
Console.WriteLine(string.Format("There are {0} prime numbers below {1}, they are {2}", result.Length, upperLimited, string.Join(",", result))); //optional
return result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment