Skip to content

Instantly share code, notes, and snippets.

@gideondsouza
Created March 5, 2012 15:49
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save gideondsouza/1978926 to your computer and use it in GitHub Desktop.
Save gideondsouza/1978926 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes C# implementation
long sum = 0;
long n = 2000000;
bool[] e = new bool[n];//by default they're all false
for (int i = 2; i < n; i++)
{
e[i] = true;//set all numbers to true
}
//weed out the non primes by finding mutiples
for (int j = 2; j < n; j++)
{
if (e[j])//is true
{
for (long p = 2; (p*j) < n; p++)
{
e[p * j] = false;
}
}
}
//Uptill here e[] sorta of contains a list of primes
//the index represent the actual number and the value at the index represents if the number is prime
//Example:
//e[4], e[100] will all be false since 2,4,100 are not primes
//e[5], e[7], e[11], e[13] will all be true because 5,7,11,13 are all prime numbers
@MHenley
Copy link

MHenley commented Jan 13, 2014

2 is the first prime number.

@milesperhour
Copy link

If you set the first for loop to start at 3 and increment by 2, you'll weed out even numbers (which aren't prime)

@Shigetorum635
Copy link

Weird things

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment