Created
August 24, 2012 09:32
-
-
Save prabhuignoto/3448201 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes
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
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
using System.Diagnostics; | |
namespace EratosthenesPrimeSieve | |
{ | |
class Program | |
{ | |
static int[] numbers = new int[100000000]; | |
static int maxNumber; | |
static void Main(string[] args) | |
{ | |
Console.WriteLine("Please enter a max number "); | |
maxNumber = int.Parse(Console.ReadLine()); | |
Stopwatch sw = new Stopwatch(); | |
sw.Start(); | |
for (int num = 2; num < maxNumber + 1; num++) | |
numbers[num-2] = num; | |
sw.Stop(); | |
Console.WriteLine("Array fill complete. Time elapsed :" + | |
(double)sw.ElapsedMilliseconds/1000); | |
sw.Restart(); | |
for(int idx=0;idx<maxNumber-3;idx++) | |
{ | |
int num=numbers[idx]; | |
if (num != 0) | |
{ | |
while (num+idx < maxNumber ) | |
{ | |
numbers[idx + num] = '\0'; | |
num += numbers[idx]; | |
} | |
} | |
} | |
sw.Stop(); | |
Console.WriteLine("Removed all non primes from the array. Time elapsed :" + | |
(double)sw.ElapsedMilliseconds/1000 + "\n" + | |
"Press enter to display all the primes upto "+maxNumber ); | |
IEnumerable<int> result= numbers.Where(num => num != 0); | |
Console.WriteLine("Primes found :" + result.Count()); | |
Console.ReadLine(); | |
Parallel.ForEach(result, p => Console.Write(p + ",")); | |
Console.ReadLine(); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment