Created
March 5, 2012 15:49
-
-
Save gideondsouza/1978926 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes C# implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
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)
Weird things
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 is the first prime number.