Skip to content

Instantly share code, notes, and snippets.

@prabhuignoto
Created August 24, 2012 09:32
Show Gist options
  • Save prabhuignoto/3448201 to your computer and use it in GitHub Desktop.
Save prabhuignoto/3448201 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes
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